Merge Sort

Merge Sort is a divide-and-conquer sorting algorithm that works by splitting the input list into two halves, sorting each side, before finally merging them. It is driven by the merge subroutine, which is responsible for merging the two halves into a single sorted list.

The key insight of Merge Sort is that the sub-lists that are provided to merge are already sorted. This is because inductively, the two halves have already been sorted (because merge is called after the recursive calls). This means that we can simply move the elements fromt he left and right halves into the original list, and we’re done.

In the event that the left and right halves are of unequal size, we drain them into the list at the end.

Time complexity analysis

As the elements in the input list are divided in half at each step, the number of recursive calls is logarithmic at . The merge subroutine has a time complexity of as can be seen in the final call to merge with the entire list. Therefore, the total time complexity of Merge Sort is .

Space complexity analysis

Merge Sort copies over the left and right halves of the input list into temporary arrays. For recursive call , the size of the left and right halves are . Summing these up gives us the space complexity of .

Implementation

Java Implementation

package jun.codes.interviews.sort;

import java.util.Arrays;

public class MergeSort {
  public static <T extends Comparable<T>> void sort(T[] xs) {
    sort(xs, 0, xs.length - 1);
  }

  public static <T extends Comparable<T>> void sort(T[] xs, int low, int high) {
    // If the low and high indices have not crossed each other, then we can
    // continue the sort. In other words, there are more items to sort
    if (low < high) {
      int midpoint = (low + high) / 2;
      sort(xs, low, midpoint);
      sort(xs, midpoint + 1, high);
      merge(xs, low, midpoint, high);
    }
  }

  public static <T extends Comparable<T>> void merge(
      T[] xs,
      int low,
      int midpoint,
      int high
  ) {
    // Create temporary arrays to hold the left and right halves of the array
    T[] left = Arrays.copyOfRange(xs, low, midpoint + 1);
    T[] right = Arrays.copyOfRange(xs, midpoint + 1, high + 1);
    // Variables i and j keep track of the current index in the left and right
    // arrays, respectively. k keeps track of the current index in the sorted
    // array.
    int i = 0;
    int j = 0;
    int k = low;
    // Go through the left and right halves until either array is emptied.
    // When either array is emptied, we drain the remaining elements from them.
    // This is sound because left and right are already sorted inductively.
    while (k <= high && i < left.length && j < right.length) {
      // If left is smaller than right, then we add the left element to the
      // sorted array
      if (left[i].compareTo(right[j]) <= 0) {
        xs[k] = left[i];
        i++;
      } else {
        // Otherwise, we add the right element to the sorted array
        xs[k] = right[j];
        j++;
      }
      k++;
    }

    // Drain the left array into the original array
    while (i < left.length) {
      xs[k] = left[i];
      i++;
      k++;
    }

    // Drain the right array into the original array
    while (j < right.length) {
      xs[k] = right[j];
      j++;
      k++;
    }
  }
}

Further reading

The relevant material in Introduction to Algorithms 4th edition can be found starting on page 35.

• Wikipedia: Merge Sort