Merge Sort: Split in Half, Sort Each Half, Merge

Merge sort is a sorting algorithm that splits an array into two halves, sorts each half by calling itself on it, and merges the two sorted halves into one sorted array. This card covers the splits down to single items, the merges back up, and the signs that merge sort is the sort to reach for.

To merge two sorted halves, look at the first item of each, move the smaller one to the output, and repeat until both halves are empty. A half is sorted before it is merged, so its first item is always its smallest, and the smaller of the two first items is the smallest item left anywhere. Two sorted lists become one sorted list by looking only at their fronts.

Sorting 5 2 7 4 1 8 3 6 shows the shape. The split step finds the middle index and nothing else: it cuts the array into 5 2 7 4 and 1 8 3 6 without comparing a single item, and each half is cut again until every piece holds one item. A piece of one item is already sorted, which is the base case. The merges then run back up the tree, and each node of the tree below is a piece of the array, with what merging gave back.

A run of the code printed these seven merges, in this order: the pairs on the left, then the left four, then the pairs on the right, then the right four, and last the two sorted halves of the whole array. Read down the tree and nothing moves; read up it and every merge leaves a longer sorted piece, until the root holds the answer. This is divide and conquer with the work at the end: the split costs O(1), and each merge costs time in proportion to the items it combines.

Combining two piles of marked exam papers works the same way. Each pile is already in order of mark, lowest on top, and you build one pile by always taking whichever top paper has the lower mark. The analogy breaks on what you can see: a person can glance down a pile and lift a run of low marks in one go, while the merge sees only the two front items and moves one at a time.

Splitting by value is not merge sort. Cutting 5 2 7 4 1 8 3 6 into the four smallest items, 2 4 1 3, and the four largest, 5 7 8 6, is a partition, the step quicksort is built on, and once both sides are sorted there is nothing left to merge. Merge sort never looks at the values when it splits, so all its comparing is in the merge.

Four signs point to merge sort. You need O(n log n) guaranteed, with no slow input waiting to be found. You need a stable sort, one that keeps items with equal keys in their input order, such as records sorted by grade that must stay in name order within each grade. The data is a linked list, which cannot jump to an index but can be split and merged by following and relinking nodes. Or the data is too large for memory: sorted runs written to disk can be merged by reading only the front of each, the same look-at-the-fronts step. The price on an array is the O(n) buffer, which is why sorts that work in place still have a place.