MergeSort

MergeSort is an efficient sorting technique that is fairly easy to implement. In terms of speed, MergeSort is considerably faster than the simple sorting techniques.

A downside to MergeSort is that it requires an additional array in memory, equal in size to the one being sorted.

The "guts" of MergeSort is the merging of two already sorted arrays. Merging two sorted arrays A and B creates a third array, C, that contains all of the elements of A and B, also arranged in sorted order.

The idea behind MergeSort is to divide an array in half, sort each half, and them use a "merge" function to merge the two halves into a single sorted array.

  1. If the number of items to sort is 0 or 1, return.
  2. Recursively sort the first and second halves separately.
  3. Merge the two sorted halves into a sorted group.

Merge sort is example of a "divide-an-conquer" algorithm: divide into two equal-sized sets, and conquer by merging the two sorted sets into one.

MergeSort pseudo-code:

   mergeSort(T a[], T tmpA[], int left, int right)

      if (left == right)  return;
      mid = (left + right) / 2;
      mergeSort(a, tmpA, left, mid);
      mergeSort(a, tmpA, mid+1, right); 

      for (i = left; i <= right; i++) tmpA[i] = a[i];
      i1 = left, i2 = mid + 1;

      for (int cur_i = left;  cur_i <= right; cur_i++) {
         if (i1 == mid + 1)
            a[cur_i] = tmpA[i2++];
         else if (i2 > right)
            a[cur_i] = tmpA[i1++];
         else if (tmpA[i1] < tmpA[i2])
            a[cur_i] = tmpA[i1++];
         else
            a[cur_i] = tmpA[i2++];
    }