Search

0.3.2.3 Source Code

The Mergesort, implemented in C, follows:

void mergesort (int *array, int left, int right) {
  if (left < right) {
    merge_sort (array, left, (left+right)/2);
    merge_sort (array, (left+right)/2 + 1, right);
    merge (array, left, (left+right)/2, (left+right)/2+1, right);
  }
}


void merge (int *A, int first1, int last1, int first2, int last2) {
  int temp[MAX_ARRAY];
  int index, index1, index2;
  int num;

  index = 0;
  index1 = first1;
  index2 = first2;

  num = last1 - first1 + last2 - first2 + 2;

  /*
   *  Merge the two lists back together until one list runs out of
   *  items...
   *
   */

  while ((index1 <= last1) && (index2 <= last2)) {
    if (A[index1] < A[index2]) temp[index++] = A[index1++];
    else temp[index++] = A[index2++];
  }
 
  /*
   *  At which point fill in the merged list with the "rest" of the
   *  non exhausted list.
   *
   */

  if (index1 > last1)
    move (A, index2, last2, temp, index);
  else 
    move (A, index1, last1, temp, index);

  
  /* finally move our merged array in temp space to the real array */
  move(temp, 0, num-1, A, first1);
}


void move (int *list1, int first1, int last1, int *list2, int first2) {
  while (first1 <= last1)
    list2[first2++] = list1[first1++];
}