A Deep Dive Into Merge Sort

Merge Sort

Pseudocode

Analysis

• Because Merge Sort divides the list first, an even split is guaranteed.
• After the recursion, a linear amount of work is done to merge the two sublists.
• Basic idea:
  • Maintain two index pointers, one for each sublist.
  • Compare the elements pointed to, copy the minimal element to the destination, and advance the corresponding pointer.
  • Continue until one sublist is exhausted, then copy the remaining elements of the other sublist.
• Requires the use of an $O(n)$-sized temporary array.
• Recurrence relation: $$C(n)=2C\frac{n}{2}+n$$
• By the Master Theorem, the time complexity is $O(n \log n)$.
• In fact, this performance is guaranteed (best, worst, and average cases are all the same).

Code Samples

Code Sample 18: Java Merge Sort for integers

public static void mergeSort(int[] a, int low, int high)
{
  if (low < high) {
    int middle = (low + high) / 2;
    mergeSort(a, low, middle); // Recursively sort the left half
    mergeSort(a, middle + 1, high); // Recursively sort the right half
    merge(a, low, middle, high); // Merge the two sorted halves
  }
}

Code Sample 19: Java Merge for integers

private static int[] MERGE_HELPER;
//... ensure MERGE_HELPER is initialized with correct size before calling merge ...

private static void merge(int[] a, int low, int middle, int high)
{
  // Copy both parts into the helper array
  for (int i = low; i <= high; i++) {
    MERGE_HELPER[i] = a[i];
  }
  int i = low;
  int j = middle + 1;
  int k = low;
  // Copy the smallest values from the left or the right side back to the original array
  while (i <= middle && j <= high) {
    if (MERGE_HELPER[i] <= MERGE_HELPER[j]) {
      a[k] = MERGE_HELPER[i];
      i++;
    } else {
      a[k] = MERGE_HELPER[j];
      j++;
    }
    k++;
  }
  // Copy the rest of the left side of the array into the target array
  while (i <= middle) {
    a[k] = MERGE_HELPER[i];
    k++;
    i++;
  }
  // Copy the rest of the right side of the array into the target array
  while (j <= high) {
    a[k] = MERGE_HELPER[j];
    k++;
    j++;
  }
}

Code Sample 20: C Merge Sort for integers

void mergeSort(int *array, int left, int right)
{
  int mid = (left + right) / 2;
  /* We have to sort only when left < right because when left = right it is already sorted */
  if(left < right)
  {
    /* Sort the left part */
    mergeSort(array, left, mid);
    /* Sort the right part */
    mergeSort(array, mid + 1, right);
    /* Merge the two sorted parts */
    merge(array, left, mid, right);
  }
}