Expert: Zlatko - 11/17/2010

Question
So I'm trying to sort people by thier order number in my program. I have to use the merge sort. I understand what the functions do that are required to do the merge sort, but for some reason when I call it in main, its not working properly. The all is from the people struct that I have.

//this is what I'm calling in main
MergeSort(all[j].orderNum, 0, group-1);

void MergeSort(int values[], int start, int end) {

   int mid;
 
   // Check if our sorting range is more than one element.
   if (start < end) {

       mid = (start+end)/2;
   
       // Sort the first half of the values.
       MergeSort(values, start, mid);
   
       // Sort the last half of the values.
       MergeSort(values, mid+1, end);
   
       // Put it all together.
       Merge(values, start, mid+1, end);
   }
}
//---------------------------------------------
void Merge(int values[], int start, int middle, int end) {

   //printf("merge %d, %d, %d
", start, middle, end);
   
   int *temp, i, length, count1, count2, mc;
 
   // Allocate the proper amount of space for our auxiliary array.
   length = end - start + 1;
   temp = (int*)calloc(length, sizeof(int));

   // These will be our indexes into our two sorted lists.
   count1 = start;
   count2 = middle;
 
   // Keeps track of our index into our auxiliary array.
   mc = 0;

     while ((count1 < middle) || (count2 <= end)) {

       // Next value to copy comes from list one - make sure list
       // one isn't exhausted yet. Also make sure we don't access index
       // count2 if we aren't supposed to.
       if (count2 > end || (count1 < middle && values[count1] < values[count2])) {
           temp[mc] = values[count1];
           count1++;
           mc++;
       }
   
       // We copy the next value from list two.
       else {
           temp[mc] = values[count2];
           count2++;
           mc++;
       }
   }

   // Copy back all of our values into the original array.
   for (i=start; i<=end; i++)
       values[i] = temp[i - start];

   // Don't need this space any more!
   free(temp);
}
//-------------------------------------------------
int Is_Sorted(int values[], int length) {
   
   int i;
   
   // Return false if out of order.
   for (i=0; i<length-1; i++)
       if (values[i] > values[i+1])
           return 0;
           
   return 1;
}

so why would the function call not be working?

Answer
Hello Sam
I believe your sort is correct. I have tested it with an array of random integers of various sizes, and it works.

I think you are not calling it correctly.

You seem to have an array of structures and you want to sort the array on the orderNum.

You will need to change merge sort to accept an array of your structures, not an array of integers. In Merge you will need to do comparisons based on the orderNum field in the structure.

That should get you the right result.

Best regards
Zlatko