Mergesort — Stable O(n log n) Sort With Predictable Behavior

The algorithm, and where n log n comes from

Split the input in half, sort each half recursively, then merge the two sorted halves into one. The base case is a sequence of length one, which is already sorted. That is the entire algorithm; everything else is implementation.

The cost follows from the recurrence T(n) = 2T(n/2) + O(n): two subproblems of half the size, plus a linear merge. Expanding it gives log2(n) levels of recursion, each doing O(n) total work across all the merges at that level, so O(n log n). The useful thing about this derivation is that it does not depend on the data at all -- the split is positional, not value-based, so the recursion tree is the same shape for every input of a given size. That is precisely why there is no worst case to engineer around, and precisely why mergesort cannot exploit data that is already nearly sorted unless you add machinery for it, which is what TimSort does.

The comparison count is close to the information-theoretic lower bound. Any comparison-based sort needs at least log2(n!) comparisons, about n log2(n) - 1.44n; mergesort uses at most n log2(n) - n + 1. There is very little room left, which is worth remembering when someone proposes a cleverer comparison sort: the remaining gains are in constants, memory traffic and adaptivity, not in asymptotics.

The merge step, and exactly where stability comes from

Merging is the whole algorithm's engine. Walk two sorted sequences with one index each, repeatedly appending the smaller head to the output, then append whatever remains when one side empties.

def merge(a, lo, mid, hi, buf):
    i, j, k = lo, mid, lo
    while i < mid and j < hi:
        if a[j] < a[i]:      # strictly less -- this is the stability line
            buf[k] = a[j]; j += 1
        else:
            buf[k] = a[i]; i += 1
        k += 1
    while i < mid: buf[k] = a[i]; i += 1; k += 1
    while j < hi:  buf[k] = a[j]; j += 1; k += 1
    a[lo:hi] = buf[lo:hi]

The comparison on the marked line is the entire stability guarantee. Because the test is strictly less-than on the right-hand element, ties resolve in favour of the left half -- and the left half holds the elements that came first in the original input. Flip it to <= and the algorithm still sorts correctly and is no longer stable. Two characters, and one of mergesort's defining properties.

Stability matters whenever records are sorted more than once. Sort employees by name, then by department, and with a stable sort the result is departments in order with names still ordered inside each -- so multi-key sorting composes from single-key sorts applied in reverse order of significance. With an unstable sort the first pass is destroyed by the second. It also matters when equal keys carry meaning the comparator cannot see: arrival order in a queue, line numbers in a file, insertion order in a UI list.

Top-down and bottom-up

The recursive form above is top-down: split, recurse, merge. It is the clearest expression of the idea and it carries recursion overhead plus stack depth of log n.

The bottom-up form skips the recursion. Treat the array as n sorted runs of length one, then merge adjacent pairs to get runs of length two, then four, doubling until one run covers everything.

width = 1
while width < n:
    for lo in range(0, n, 2 * width):
        mid = min(lo + width, n)
        hi  = min(lo + 2 * width, n)
        merge(a, lo, mid, hi, buf)
    width *= 2

Same comparisons, same complexity, no call stack, and the loop structure makes the memory access pattern obvious -- which matters, because it is a purely sequential sweep at every width. Bottom-up is generally the better choice for arrays and the natural choice when you are sorting on hardware where recursion is expensive or unavailable. Top-down keeps an advantage in one respect: it can stop early on a subarray that is already in order, and it is easier to hybridise with a small-array sort at the base of the recursion.

That hybrid is standard practice. Below a threshold of roughly 16 to 32 elements, insertion sort beats mergesort by a wide margin -- it has almost no overhead and it is excellent on the nearly-sorted small ranges the recursion produces. Every serious implementation cuts over, and the cutover is worth more than most other micro-optimisations put together.

The auxiliary array, and how to stop paying for it repeatedly

Mergesort needs somewhere to put the merged output, because a merge cannot safely overwrite its own inputs. The naive implementation allocates a temporary array inside merge, which means O(n log n) allocations over the sort -- and on a managed runtime, that allocation pressure typically costs more than the comparisons.

The first fix is to allocate one buffer of size n up front and pass it down. The second, better fix is to alternate roles: merge from the source array into the buffer at one level of the recursion, and from the buffer back into the source at the next, so the copy-back at the end of every merge disappears entirely. It is a small amount of index bookkeeping and it removes a linear copy per merge, which is a measurable fraction of total runtime.

Truly in-place merging exists -- block-based rotation merges achieve O(1) extra space -- but the constants are poor enough that the technique is reserved for memory-constrained environments rather than used by default. The practical position for most systems is that O(n) auxiliary space is acceptable for arrays and unnecessary for linked lists, which merge in place naturally.

One structural consequence: sorting a large array with mergesort briefly needs about twice the memory of the data. On a service sorting multi-gigabyte batches, that doubling is a capacity-planning fact, and it is a common reason implementations fall back to an in-place algorithm when the input exceeds a threshold.

Linked lists, where mergesort is simply the right answer

For a linked list, mergesort is not a compromise -- it is the natural sort. Merging two sorted lists requires only pointer reassignment, so the O(n) auxiliary array vanishes and the extra space is O(1) for the bottom-up form or O(log n) stack for the recursive one.

The other classical sorts fare badly here. Quicksort needs random access for partitioning around a pivot chosen by position, and picking a pivot in a list means walking it. Heapsort needs indexable random access outright. Insertion sort works on a list and is quadratic. This is why mergesort is what standard-library list sorts use, and it is worth knowing when a data structure -- an intrusive list in a kernel, a free-list, a chain of buffers -- has to be sorted without being copied into an array.

The splitting step is the only fiddly part: without indices you find the midpoint with the two-pointer trick, advancing one pointer twice as fast as the other, then cut the list there. Bottom-up avoids even that by merging runs of doubling length off the front of the list, which is the version to use when the list is long enough that the midpoint walk is a real cost.

TimSort — mergesort that exploits the data

Plain mergesort ignores existing order. Real data rarely lacks it: log files are nearly sorted by time, database results arrive partly ordered, appended records extend an already-sorted prefix. TimSort is the adaptive mergesort built around that observation, and it is what Python's sort and Java's Arrays.sort for objects actually run.

It works in three moves. First it scans for natural runs -- maximal already-ordered stretches, with descending stretches detected and reversed in place (strictly descending, so that reversing preserves stability). Second, short runs are extended to a computed minimum length using binary insertion sort, so the number of runs to merge stays close to a power of two and the merge tree stays balanced. Third, runs are pushed on a stack and merged according to invariants that keep run lengths roughly balanced, so no single merge is wildly lopsided.

The optimisation that earns most of its speed is galloping. When one run keeps winning the comparison, the merge switches from stepping one element at a time to exponential search for the position where the other run's next element belongs, consuming a long block in O(log k) comparisons instead of k. On concatenated sorted data -- merging yesterday's file with today's -- this turns the merge close to linear-with-tiny-constant.

The result is O(n) on already-sorted input, O(n log n) worst case, and stability throughout. There is a good historical footnote here: TimSort's merge-stack invariants were found in 2015 to be subtly insufficient by researchers applying formal verification, producing an array-index exception on certain adversarial run-length sequences after the algorithm had been in production in two major runtimes for years. It was fixed by correcting the invariant check. The lesson is not that TimSort is fragile -- it is that merge-order invariants are exactly the kind of thing testing does not reach.

External sorting — the reason mergesort survives at scale

When the data exceeds memory, random access becomes disk or network access and every in-memory algorithm's cost model breaks. Mergesort adapts because its access pattern is sequential, which is the one thing external storage does well.

External merge sort has two phases. In the run generation phase, read as much as fits in memory, sort it in memory, write it out as a sorted run, and repeat until the input is consumed. This yields roughly n/M runs for memory size M. In the merge phase, open several runs at once and merge them with a min-heap over the current head of each run, writing one output stream.

The tuning parameter is the merge fan-in. Higher fan-in means fewer passes over the data -- the number of passes is log_k(n/M) for fan-in k -- but each open run needs an input buffer, so buffers shrink as fan-in grows and reads become less sequential. The optimum trades pass count against read size, and on spinning disks it favoured large buffers strongly; on flash it has shifted towards higher fan-in. A well-configured system usually needs two passes and occasionally three.

This is not a historical curiosity. It is what a database does for an ORDER BY that exceeds the sort buffer, what a sort-merge join does to both of its inputs, what a shuffle in a distributed processing engine does when a partition spills, and what the classic command-line sort utility does with large files. A surprising fraction of the total I/O in an analytics cluster is external mergesort.

Parallel mergesort

Mergesort parallelises more naturally than quicksort because the split is positional and known in advance: two independent halves can be sorted on two threads with no coordination, then merged. The recursive structure maps directly onto a fork-join framework, and standard libraries expose it -- a parallel sort call on an array is typically a parallel mergesort.

The catch is the final merge. Sorting the halves in parallel is easy; merging them is inherently sequential in the naive formulation, and Amdahl's law then caps the speedup regardless of core count. The fix is a parallel merge: take the median of the larger run, binary-search for its position in the smaller run, and the two resulting pairs of subranges can be merged independently. Recursing on that split makes the merge itself parallel, at the cost of a more elaborate implementation and extra bookkeeping.

Practical guidance: parallel sorting pays off on large arrays of objects with expensive comparators, and often does not pay off on small arrays or cheap primitive comparisons, where the coordination overhead and the memory bandwidth ceiling dominate. Sorting is memory-bound long before it is CPU-bound, so eight threads rarely give anything like eight times the throughput. Measure on the real data size before committing to it.

What else the merge can compute

The merge visits every pair of runs in a known order, which makes it a place to hang extra computation for free. The classic example is counting inversions -- pairs that are out of order relative to each other, which is a standard measure of how unsorted a sequence is and appears in ranking-correlation statistics.

The trick is one line. During a merge, when an element from the right half is taken before elements remain in the left half, every one of those remaining left elements forms an inversion with it. So add the count of remaining left elements to a running total at that moment, and mergesort computes the inversion count as a side effect in O(n log n) -- against O(n^2) for the obvious double loop.

if a[j] < a[i]:
    inversions += (mid - i)     # every remaining left element beats a[j]
    buf[k] = a[j]; j += 1

The same hook answers a family of related questions: how many elements to the right of each position are smaller than it, how many pairs differ by more than some bound, and range-restricted counting when combined with a merge-sort tree, which stores the sorted version of every recursion node so that a query range decomposes into a handful of sorted lists to binary-search.

This generalises into a useful habit. Divide-and-conquer with a linear combine step can compute anything expressible as 'contribution within the left, plus contribution within the right, plus cross-boundary contribution'. Inversion counting is the cross-boundary term for orderedness; the closest pair of points, the maximum subarray, and counting range sums all have the same shape.

Mergesort against quicksort and heapsort

Quicksort is typically faster in memory despite identical asymptotic average cost. It partitions in place, so it has no auxiliary array and no copy-back, and its inner loop is exceptionally cache-friendly. Its weaknesses are a quadratic worst case on adversarial or pathological input, instability, and recursion depth that must be controlled. Production implementations use introsort -- quicksort with a depth limit that switches to heapsort -- to bound the worst case while keeping the fast path.

Heapsort guarantees O(n log n) with O(1) extra space, which sounds strictly better than both. In practice it is the slowest of the three on real hardware because its access pattern jumps around the array by powers of two, which defeats the cache and the prefetcher. It is unstable. Its real role is as a worst-case backstop and in embedded contexts where the space bound is binding.

The decision rule that most standard libraries have converged on is instructive: use an introsort variant for primitives, where stability is meaningless because equal primitives are indistinguishable, and use a TimSort-style stable mergesort for objects, where stability is observable and comparators are expensive enough that saving comparisons matters more than saving memory traffic. Java does exactly this split, and the reasoning generalises: if you cannot tell two equal elements apart, stability buys nothing; if you can, it is usually required.

Practical notes

Use the library. The standard sort in any mature runtime is a hybrid, heavily tuned, and correct in edge cases your implementation will not be. Write mergesort yourself when you are sorting a structure the library does not cover (an intrusive list, a memory-mapped region, a stream of runs from disk), or when you need the merge step specifically rather than the sort.

The merge is more useful than the sort. Merging k sorted streams with a heap is the core of external sorting, of log aggregation across shards, of combining sorted posting lists in a search index, and of the sorted-run merge inside every LSM-tree compaction. If you understand the merge, you understand the machinery underneath a lot of storage systems.

Watch the comparator. An inconsistent comparator -- one that is not transitive, or that says two elements are both less than each other -- produces undefined results, and some implementations detect the violation and throw rather than returning garbage. This is a far more common bug than any sorting-algorithm choice, and it usually comes from comparing floating-point values that can be NaN, or from subtracting integers to produce an ordering and overflowing.

Consider not comparing at all. For fixed-width integer or string keys, radix sort is O(nk) and beats every comparison sort on large inputs by dodging the n log n bound entirely. It is not general and it is not always stable unless implemented carefully, but for the specific case of sorting a hundred million integers it is the right tool.