merge sort with fork() and wait()

[fireatmyself]

Greetings to everyone!

As the topic title states, I want to implement merge sort, using child processes, but I can't get it right. My algorithm looks like this:

void merge(int arr[], int beg, int end, int pid1, int pid2)
{
  int mid = (beg+end)/2, i = 0, *v, lo = beg, hi = mid+1;
  
  if (beg>=end) return;
  
  merge(arr, beg, mid); //this must be executed by a child process
  merge(arr, mid+1, end); //this must be executed by another child process
  
  //merge left and right - this must be executed after both child processes finish
  v = (int *)malloc(sizeof(int)*(end-beg+11));
  
    while ((lo<=mid)&&(hi<=end))
      if (arr[lo]<arr[hi]) v[i++] = arr[lo++];
      else v[i++] = arr[hi++];
      if (lo<=mid)
        for (hi = lo; hi <= mid; hi++) v[i++] = arr[hi];
      else
        if (hi<=end)
          for (lo = hi; lo <= end; lo++) v[i++] = arr[lo];
    for (i=beg, lo=0; i<=end; i++) arr[i] = v[lo++];
    free(v);
}

How am I suppose to write this? May you help me?

Cheers.

[iMalc]

I'm pretty sure that you don't want separate processes sorting the data at once!!! What you want is merely different threads working on it at once. Perhaps try to get started using pthreads.

[MK27]

I'm pretty sure that you don't want separate processes sorting the data at once!!! What you want is merely different threads working on it at once. Perhaps try to get started using pthreads.

Ditto. fork() will never work here for this, because the child receives a copy of the parent -- what happens in the child does not happen in the parent. So the children finish, but they never return anything to the parent.

[slingerland3g]

Ditto. fork() will never work here for this, because the child receives a copy of the parent -- what happens in the child does not happen in the parent. So the children finish, but they never return anything to the parent.

Was thinking that would not work at all. My question, is, as this interest me - for the OP, is why are you needing to implement threads for this, I do not see how this will make mergesort() any faster, unless that is not the goal here. Also if you were to implement any fork() process for this, that would just explode the resource consumption.

Granted I do not have much experience with forking of processes much. Interested in how this post will end.

[MK27]

Was thinking that would not work at all. My question, is, as this interest me - for the OP, is why are you needing to implement threads for this, I do not see how this will make mergesort() any faster, unless that is not the goal here.

Hmm, I've never used threading for this but I assume it will allow you to max out several processors instead of just one. The initial split in mergesort seems a perfect opportunity for that.

[fireatmyself]

So is there a way to make recursion (in this particular case, merge sort) using forks?

I tried something like this ...

...

  pid1=fork();
  if (pid1<0) exit(0); //error in creating child process
  if (pid1==0) //child process
         merge(arr, beg, mid);
  else wait();
  
  pid2=fork();
  if (pid2<0) exit(0); //error in creating child process
  if (pid2==0) //child process
        merge(arr,mid+1,end);
  else wait();

  if (pid1>0&&pid2>0) //I figured this is the condition for both child processes to terminate
  {
    v = (int *)malloc(sizeof(int)*(end-beg+11));
    while ((lo<=mid)&&(hi<=end))
    ...
  }

... yet it doesn't work quite well...

[MK27]

So is there a way to make recursion (in this particular case, merge sort) using forks?

NO!!!

It doesn't matter how you try it. fork() launches a separate process. Trying to do a mergesort that way is like saying you will write three programs:

-program A divides the unsorted list, then gives half to program B, and half to program C.
-program B sorts the first half.
-program C sorts the second half.
-all three programs are now complete.

Guess what? You cannot join the two halves together that way UNLESS you do some "Inter Process Communcation". That could be as simple as:

-program B and C both write their sorted lists to seperate files. Then program A reads the files and merges the lists, OR
-program A opens a server socket, then programs B and C connect and transmit their sorted lists (one at a time) to program A, which merges them.

There are some other possibilities here but they are just as ridiculous. Do you think this will make for a more efficient sort? It might, if the list is very very big, but it would be simpler to just learn to use threads, which will be better in all cases.

Write this out 100 times:

FORKED PROCESSES DO NOT SHARE ANY MEMORY. FORKED PROCESSES DO NOT SHARE ANY MEMORY. FORKED PROCESSES DO NOT SHARE ANY MEMORY...

[iMalc]

So is there a way to make recursion (in this particular case, merge sort) using forks?

I tried something like this ...

... yet it doesn't work quite well...

If you're going to repeat yourself instead of listening to what we're telling you, then I'm going to repeat myself as well, perhaps a little more clearly this time:

You don't want separate processes sorting their own copy of data at once, which is what fork() would do!
What you want is merely different threads working on the same data at once.
Google for "pthreads" or use whatever the native threading API is on your platform.

[fireatmyself]

Thank you both for your time.