Merge Sort: Divide, Sort, Merge

Merging two already-sorted lists is simple: compare the two front items, take the smaller, repeat. It needs one pass and no backtracking. Merge sort turns that into a full sort. Split the list in half, sort each half, then merge them. To sort each half, apply the same idea again. A list of one item is already sorted, which stops the recursion.

This is divide and conquer: split the problem, solve the parts, combine the answers. The work lives in the combine step; splitting only finds the middle index.

Here is a run on the eight numbers from the diagram below, printed by an instrumented copy of the next section's code, one line per merge:

The recursion goes depth first, so the left half is done before the right is split. Count the comparisons: 1 for each one-item merge, 3 for each four-item merge and 7 for the last, 17 in total. A merge of m items needs at most m - 1 comparisons, reached when the halves interleave to the end. This input interleaves at every level, and trying all 40,320 orderings of eight items confirms 17 is the most this code ever spends.

The <= in the comparison matters. When two items are equal, the one from the left half goes first, so equal items keep their original order. That is what makes the sort stable.

The base case is len(a) <= 1, so an empty list returns at once. On odd lengths, len(a) // 2 puts the extra item in the right half, which is fine as long as both halves shrink. And the function returns a new list, unlike list.sort, which sorts in place and returns None.

The slices copy items, so every level copies all n items before merging. A tighter version passes index bounds and merges into one buffer allocated once. Recursion depth is about log2 n: 17 levels for 100,000 items, far below Python's default limit of 1,000.

Halving a list of n items takes about log2 n levels before pieces have one item. At every level, merging touches each item once, so a level costs O(n). Total work is n multiplied by log2 n. As a recurrence, T(n) = 2T(n/2) + cn, which solves to Θ(n log n).

I counted the comparisons on random floats, then on the same values sorted and reversed. Each list is drawn fresh from seed 42:

Random input lands a little under n log2 n. The exact worst case for this version is n⌈log2 n⌉ − 2^⌈log2 n⌉ + 1, which is 123,617 for 10,000 items, and random merges usually empty one side a few items early.

Sorted input costs about half. Each merge finds the whole left half smaller than the right, makes one comparison per left item, then copies the right half unread. Reversed input is the mirror case, one comparison per right item, and since right halves get the extra item it costs slightly more (69,008 against 64,608).

Unlike quicksort, there is no bad input: sorted, reversed and random data all cost Θ(n log n). There is no good input either, which is the gap Timsort closes.

A sort is stable if records with equal keys come out in the order they went in. I sorted 10,000 pairs of (key, original position) by key only and compared with Python's built-in stable sort:

The results were identical, which confirms the <= merge is stable.

Then I changed <= to <. The keys still came out in order, so an "is it sorted?" test passes. The positions did not: of the 9,949 neighbouring pairs sharing a key, all 9,949 came out in reverse input order, because strict < sends every tie to the right half. Only a test that tracks positions catches it.

Stability matters when you sort by several fields in turn. Sort by name, then stable-sort by city, and people in the same city stay ordered by name. Quicksort and heapsort are not stable in their usual forms.

The merge step writes into a separate output list, so array merge sort uses O(n) extra memory. In-place array versions exist but are complicated and slower in practice. Quicksort and heapsort sort in place, which is why they are often chosen for arrays in memory.

On linked lists the story changes. Merging linked lists only relinks nodes, and merge sort needs no random access, so it is the usual choice there; a slow and a fast pointer find the middle in one pass. The Linux kernel's list_sort is a merge sort.

The recursion can go too. Bottom-up merge sort merges runs of 1 into runs of 2, then 4, until one run remains:

It matched sorted() on random lists of size 0, 1, 2, 7, 1,000 and 1,023. The odd sizes matter, since a pass can end with a short run or one with no partner.

Merge sort also handles data too big for memory: sort chunks, write them out, and merge the sorted files. That is external sorting, which databases use; PostgreSQL's EXPLAIN ANALYZE shows an on-disk method such as Sort Method: external merge when a sort outgrows work_mem. Merging k files with a min-heap of their front items costs O(n log k).

Python's sorted and list.sort use Timsort, and Java uses it for objects (primitive arrays get a dual-pivot quicksort, since equal ints cannot be told apart). Timsort is a merge sort variant that finds runs already in order and merges them, so nearly sorted input is handled in close to linear time while the worst case stays O(n log n). It is stable by design.

A counting __lt__ wrapper shows the difference. On make_random(10_000), Timsort made 120,235 comparisons and the merge sort above 120,431. On that list sorted, Timsort made 9,999, which is n − 1: one pass finds a single run. Reversed input also cost 9,999, because a strictly descending run is simply reversed. Then 10 swaps went into the sorted list:

On the result Timsort needed 10,945 comparisons and plain merge sort 80,662.

On the test machine (best of three), the Python merge sort took 0.301 s on make_random(100_000) and sorted took 0.0181 s, about 17 times faster, mostly because the built-in runs in C.

When would you write your own? Mostly for learning, or for counting inversions, the pairs i < j with a[i] > a[j]:

On 8 3 5 1 7 2 6 4 it returns 16, matching a brute-force check of all 28 pairs. When right[j] is taken it is smaller than every item still in left, so it closes len(left) - i inversions at once, turning an O(n^2) count into O(n log n).

Forgetting the tail. The loop stops when one side is empty, so the rest of the other side must be appended. Drop + left[i:] + right[j:] and nothing crashes. On [2, 1] the result is [1], and on 8 3 5 1 7 2 6 4 it is also [1], because every merge discards its leftovers.

Index-based splits. With an exclusive hi, the base case is hi - lo <= 1 and the halves are [lo, mid) and [mid, hi); mixing conventions skips an item or recurses forever. In Java or C, write mid = lo + (hi - lo) / 2, because (lo + hi) / 2 can overflow a 32-bit int. Joshua Bloch described this in 2006 in "Nearly All Binary Searches and Mergesorts are Broken", after it turned up in the JDK's binary search.

Values with no order. Every comparison with NaN is false. Sorting [3, nan, 1, 2] with the code above gave [1, 2, nan, 3], and Python's sorted returned the list unchanged. Mixed types fail louder: [1, "a"] raises a TypeError. Clean such values first.

Q: What is the time complexity of merge sort?
A: Θ(n log n) in best, average and worst case: about log2 n levels, each with O(n) merge work. Extra space is O(n) for arrays.

Q: Is merge sort stable?
A: Yes, if the merge takes from the left half on ties (<=). With < the keys still sort, but equal items come out reversed.

Q: Merge sort or quicksort?
A: Merge sort guarantees O(n log n) and is stable but needs extra memory on arrays. Quicksort is usually faster in memory and in place but has an O(n^2) worst case.

Q: Best choice for a linked list?
A: Merge sort, because merging needs only pointer changes and no random access.

Q: How do you sort a file bigger than memory?
A: External merge sort: sort chunks that fit, write each run to disk, then merge the runs with a min-heap in O(n log k) for k runs.

Q: How do you count inversions in O(n log n)?
A: During the merge, each time an item comes from the right half, add the number of items still in the left half.