Merge Sort & the Divide-and-Conquer Pattern

The three sorts from the last chapter share a limitation: they all make progress one element at a time, which caps them at O(n²). Merge sort breaks that ceiling with a different strategy entirely - divide-and-conquer. Instead of comparing elements directly against each other across the whole array, it splits the problem in half, recursively solves each half, and then does one relatively cheap merge step to combine the (already-sorted) halves into a fully sorted whole.

A list of length 0 or 1 is already sorted by definition - that is the base case. Anything longer gets split into a left half and a right half, and each half is sorted the same way, recursively, until the recursion bottoms out at those trivial base cases.

The real work happens in the merge step. Given two lists that are each already sorted, you can produce a single sorted list in one linear pass: keep a pointer into each list, repeatedly take whichever front element is smaller, and advance that pointer. Once one list runs out, append whatever remains of the other - it is already in order.

The recursion splits the array in half at every level, so there are log₂(n) levels of splitting. At each level, the merge steps across that level do a combined O(n) amount of work (every element gets looked at once during merging). Multiply the two together and you get O(n log n) - and critically, this holds no matter what the input looks like. Unlike quicksort in the next chapter, merge sort has no "unlucky" input that degrades it, because the split point is always the midpoint, never data-dependent.

• -Time complexity: O(n log n) in the best, average, and worst case - a genuine guarantee, not just a typical case.
• -Space complexity: O(n) extra space for the merged output arrays - merge sort is not in-place, which is its main real-world cost.
• -Stability: equal elements keep their relative order (the merge step takes from `left` on ties), which matters when you are sorting by one field but need to preserve prior ordering on another.