Merge Sort

Two teaching assistants each sort half of a stack of exam papers by score. They hand you their two sorted piles, face up. To make one sorted pile, you do not need to sort anything again. Look at the top paper of each pile, take the lower score, and repeat. Each paper costs you one glance.

That is the merge step, and it is the whole trick behind merge sort. Merging two sorted lists is cheap. So if you can get two sorted halves, you can get a sorted whole. And the way to get sorted halves is to use the same trick on each half.

#The idea: split, sort, merge

Merge sort is recursive:

1. Base case. A list of 0 or 1 items is already sorted. Return it.
2. Split the list into a left half and a right half.
3. Sort each half with merge sort.
4. Merge the two sorted halves into one sorted list.

Step 3 can look like cheating, because it calls the function you are still writing. Recursion makes it work. Every call gets a smaller list, so eventually every call hits the base case. All the real work happens on the way back up, in the merges. This pattern of splitting a problem, solving the parts and combining them is called divide and conquer.

#The merge, traced

Here is the last merge from the figure. The left half [2, 5, 6, 9] and the right half [1, 3, 7, 8] are both sorted. Pointer i marks the next item in the left half, j the next item in the right half. This is the "two lists" shape of two pointers.

i = 0, j = 0, out = []while i < len(left) and j < len(right):  if left[i] <= right[j]:    out.append(left[i]); i = i + 1  else:    out.append(right[j]); j = j + 1append what is left of left, then of right

#The code

The code is the four steps from above plus the merge you just traced. This version returns a new sorted list and leaves the input alone.

function mergeSort(a) {
  if (a.length <= 1) return a; // base case
  const mid = Math.floor(a.length / 2);
  const left = mergeSort(a.slice(0, mid));
  const right = mergeSort(a.slice(mid));
  return merge(left, right);
}
 
function merge(left, right) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    // <= takes from the left on ties: that keeps the sort stable
    if (left[i] <= right[j]) out.push(left[i++]);
    else out.push(right[j++]);
  }
  // one half is empty; the rest of the other is already sorted
  while (i < left.length) out.push(left[i++]);
  while (j < right.length) out.push(right[j++]);
  return out;
}
 
mergeSort([6, 2, 9, 5, 1, 8, 3, 7]); // [1, 2, 3, 5, 6, 7, 8, 9]

def merge_sort(a):
    if len(a) <= 1:  # base case
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)
 
def merge(left, right):
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        # <= takes from the left on ties: that keeps the sort stable
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    # one half is empty; the rest of the other is already sorted
    out.extend(left[i:])
    out.extend(right[j:])
    return out
 
merge_sort([6, 2, 9, 5, 1, 8, 3, 7])  # [1, 2, 3, 5, 6, 7, 8, 9]

#Why it is O(n log n)

Look at the figure again, row by row. Every merge row handles all n items once, so each row costs O(n). How many merge rows are there? Each split halves the size, and you can only halve n about log₂ n times before reaching single items. For 8 items that is 3 rows; for a million items, about 20.

So the total is n items × log n rows = O(n log n). For a million items, that is about 20 million steps, compared with about 500 billion for the simple sorts. And unlike insertion sort, this does not depend on the input: sorted, reversed or random, merge sort does the same splits and roughly the same work.

The price is memory. The merge writes into a new list, so merge sort needs O(n) extra space. The recursion itself only goes log n calls deep.

#Stable, if you write it right

When left[i] and right[j] are equal, the code takes the left one. Items in the left half came first in the original list, so equal items keep their original order. That makes merge sort stable, which is why it is the usual choice for sorting records by several fields.

#Common mistakes

#Check yourself

#What to practise next

Trace the full sort of [4, 1, 3, 2] by hand: two merges of pairs, then one merge of halves. Then read Quicksort, which flips the plan around: it does its work while splitting instead of while merging, and needs no extra list.