COMP1927 - Merge Sort

Merge-sort-example-300px.gif

Merge sort is a recursive divide and conquer sort. The list is halved repeatedly until each new halflist is only 1 element. The halflists are then merged back together.

The merging is done by keeping two counters, one for each halflist, and comparing the two current elements. The smallest is added to the merged list and the counter incremented.

This is repeated until all size mergedlists have been merged.

Type

Non-Adaptive; It has to split down into individual items and merge back regardless of how pre-sorted it is
Stable/Non-Stable; Depends on implementation.
Non-In-Place; It can be made to be, but it usually isn't.

Complexity

Merge sort is O(nlg(n)). We can prove this using recurrence relations. See the example there.

Example

merge-sort-image.gif

Code

void mergesort (int temp[], int array[], int start, int end) {
 
   if (end > start) {
      int mid = (start + end)/2;
      mergesort(temp, array, start, mid);
      mergesort(temp, array, mid+1, end);
 
      int a = start;
      int b = mid+1;
      int insertCounter = start; 
 
      // While each counter is still within the list
      for (insertCounter = start; (a <= mid) && (b <= end); insertCounter++) {
         // Find the smallest element 
         // (i.e. compare the elements at current counter of each list)
         // Set the position we're up to in temp to be the smallest
         // At the same time increment the counter for that list
         if (array[a] < array[b]) {
            temp[insertCounter] = array[a];
            a++;
         } else {
            temp[insertCounter] = array[b];
            b++;
         } 
      }
 
      // In this case b must have reached the end
      // Hence we just need to insert all of a into the sorted array
      while (a <= mid) {
         temp[insertCounter] = array[a];
         insertCounter++;
         a++;
      }
 
      // In this case a must have reached the end
      // Hence we just need to insert all of b into the sorted array
      while (b <= end) {
         temp[insertCounter] = array[b];
         insertCounter++;
         b++;
      }
 
      // Copy the sorted section in temp back to our array
      int i;
      for (i = start; i <= end; i++) {
          array[i] = temp[i];
      }
 
   } else {
      // This is our base case
      // We do nothing and return in order to start the merging together
   }
 
}