Q: Algorithm for concatenating N files into one in parallel in order Is there some common algorithm for choosing which files out of N files to concatenate concurrently into a single one so that they would be in order?
For example, there are 4 processes, each responsible for a single file.


*

*Process 1 does nothing. Process 2 appends file 2 at the end of file 1. Process 3 does nothing. Process 4 appends file 4 at the end of file 3.

*Process 1 does nothing. Process 2 does nothing. Process 3 appends file 3 at the end of file 1. Process 4 does nothing.

*File 1 is the resulting file.
i.e.
Step 0: 1 2 3 4
Step 1: 12 34
Step 2: 13
Step 3: 1

Given 9 processes we have
Step 0: 1 2 3 4 5 6 7 8 9
Step 1: 12 34 56 78 9
Step 2: 13 57 9
Step 3: 15 9
Step 4: 19
Step 5: 1

So, knowing only current step number and process id, I need a way to know 


*

*in how many steps we will finish given N processes/files,

*and at each step whether process id N should append its file to some other file K 

*and what that K exactly is.


i.e.
int fileToCat(int stepN, int processId, int totalNProcesses)
{
    ...
}

which returns K -- the number of file to append our file to, or negative if we don't concatenate during this step.

A: It seems like you're doing a whole lot more work than you need to. Consider, for example, your simple case of four processes and four files. Imagine the case where files 1, 2, and 3 are 250 KB each, and file 4 is 500 KB in size. In your first step:
Process 2 copies 250 KB from file 2 to file 1
Process 4 copies 500 KB from file 4 to file 3
Total for step 1: 750 kb copied

In step 2:
Process 3 copies 750 kb from file 3 to file 1

So you've moved a total of 1500 KB.
Now, consider the single-threaded case:
Process 2 copies 250 KB from file 2 to file 1
Process 3 copies 250 KB from file 3 to file 1
Process 4 copies 500 KB from file 4 to file 1

You've moved a total of 1000 KB of data.
If you're appending a bunch of files to one single file, then you're better off doing them one at a time. Doing things in parallel the way you're suggesting is going to take longer than copying one file at a time. And the more files you have to copy, the larger the difference will be in the time.
Consider your case of 9 files. We'll say that each is 100 KB in size. In the first pass, you have:
Copy file 2 to file 1 - 100 KB
Copy file 4 to file 3 - 100 KB
Copy file 6 to file 5 - 100 KB
Copy file 8 to file 7 - 100 KB
Total: 400 kb moved

Second pass:
Copy file 3 to file 1 - 200 KB - File 1 is now 400 KB
Copy file 7 to file 5 - 200 KB - File 5 is now 400 KB
Total: 400 KB moved

Third pass:
Copy file 5 to file 1 - 400 KB moved

Fourth pass
Copy file 9 to file 1 - 100 KB moved

Your total amount of data moved is 1300 KB. But if you did it one file at a time, you'd only move 800 KB of data.
If your files are large, and especially if they're all on the same physical drive, then your parallel code is going to take much longer than just doing it one file at a time. That's for two reasons:  1) the parallel version copies more data than the single-threaded version; 2) The drive can only serve one request at a time. So your parallel processes will spend most of their time waiting for some other request to finish. In other words, you won't gain any benefit.
There's certainly a way to do what you're asking (i.e. determine when which process needs to copy a file), doing so just doesn't make sense. You're creating a very complicated method of doing a simple job that can be done faster the easy way.
--
Now, that said, what you're describing is the basic algorithm for a merge sort, slightly modified. In the first pass, you start with file 1 and combine it with the next file (2). Then file 3 and combine it with the next file (4), etc.
On the second pass, you increase the skip distance. You combine file 1 with file 3. File 5 with file 7, etc. Third pass, you combine 1 with 9, 9 with 13, etc. At each step, you double the gap between files. You can write a quick loop (or recursive function) that, given the number of files, will generate the steps required. The linked merge sort article shows you how to do it, and there are approximately a gazillion merge sort implementations available online that you can download and modify.
