How can I implement a merge sort by using fork processes?

Question

Using fork processes, I want to implement merge sort. I want to divide and conquer the sorting of data in an array: I want to divide by give each half to a child process, then conquer by making the parent process merge these parts.

The following code works just for two numbers, for three or more numbers, the array does not change. Why?

void sort(int low, int high, int a[100], int b[100]) {
    int mid;
    pid_t pid1, pid2;   
    if(low < high) {
        mid = (low + high) / 2;

        pid1=fork();
        if (pid1<0) exit(0); 
        if (pid1==0) {              //first child process
            sort(low, mid,a,b);     //first half
            exit(0);
        }
        else wait(NULL);

        pid2=fork();
        if (pid2<0) exit(0);
        if (pid2==0){               //second child process
            sort(mid+1, high,a,b);  //second half
            exit(0);
        }
        else wait(NULL);

        if (pid1>0 && pid2>0)
        {
            merging(low, mid, high,a, b);

        } 
    }

}

You do realise that any two processes cannot alter the memory of the other. — Ed Heal, May 21 '17 at 08:37
[Read on fork, please](http://man7.org/linux/man-pages/man2/fork.2.html). A forked process has its own memory space, separate from the parent. Any change preforms to a sub-array in a child, isn't visible in the parent, or vice-versa. What you want is user-space threads, like the [`pthreads`](http://man7.org/linux/man-pages/man7/pthreads.7.html) library creates. — StoryTeller - Unslander Monica, May 21 '17 at 08:37
@StoryTeller pthreads are normally not user space. You generally don't care whether your thread library is user space or not as long as it can utilise multiple processors/cores. — n. m. could be an AI, May 21 '17 at 12:01

score 1 · Accepted Answer · edited May 23 '17 at 12:02

1

As has been pointed out, forked processes can neither see nor alter the memory space of each other.

You have (at least) three options:

Use forked processes and pipes (example: Fork parent child communication)
Use forked processes and shared memory (example: How to share memory between process fork()?)
Use threads (example: C threads and joining)

edited May 23 '17 at 12:02

Community

1
1

answered May 21 '17 at 13:08

SiggiSv

1,219
1
10
20

How can I implement a merge sort by using fork processes?

1 Answers1