Merge sort

Imagine two seismic services: one keeps a catalogue of earthquakes in the western hemisphere, the other in the eastern, and each records events by time. A common chronicle is needed, also by time. There is no point in throwing both catalogues into a heap and sorting them again: it is enough to look at the first unread event of each feed and take the earlier one. Below is the real USGS catalogue, all 19,073 earthquakes of magnitude 5 and up in 2015–2025, split into two feeds. The map lights up in the order in which the merge takes the events. Switch how the catalogue is split: by hemisphere or by depth.

19,073 events took 19,070 comparisons: one per event until one of the feeds ran out, and the last three events of the second feed were carried over without comparisons. Note the longest run from one feed when split into west and east: 119 events in a row came from the east. The run begins with the magnitude 8.8 earthquake off Kamchatka on 29 July 2025 and continues mostly with its aftershocks: for almost ten hours every next event of the chronicle came from the east.

Merging: two pointers

The whole of merge sort rests on one operation. Given two sorted lists, one sorted list of all their elements is needed. Keep a pointer to the first unread element of each list, compare the two elements under the pointers, move the smaller one to the result and advance its pointer. When one list runs out, move the tail of the other across whole.

Why this is correct: in each list the first unread element is the smallest of those remaining in that list, because the list is sorted. So the smallest of all remaining elements is one of the two under the pointers, and the comparison finds it. The result grows by one element per comparison, so merging lists of lengths m and k costs at most m + k − 1 comparisons and exactly m + k moves. The last comparison can always be saved: when one list has nothing left, there is nothing to compare with.

One subtlety remains: equal elements. If the first unread ones are equal, take from the left list. Then equal elements come out in the same order in which they stood, and the sort is stable. In code this is one condition: take from the right list only if its element is strictly smaller.

The idea

A list of one element is already sorted. Cut a long list in half, sort each half the same way and merge the two sorted halves into one. All the work is in the merges, and at each level of cutting they total at most n comparisons, while there are only log₂ n levels.

The recursion first breaks the array down to pieces of one element and then assembles: fours from pairs, eights from fours. It is convenient to see this as a tournament. In the first round neighbouring single pieces merge, in the second the resulting pairs, and so on until the final, where two sorted halves merge.

A tournament of merges

Here are all sixteen earthquakes of 2025 of magnitude 7 and up, in order of date. At the top, sixteen pieces of one each; each row below merges pairs of pieces from the row above. On the right of each level, how many comparisons it cost. Switch the input order: an array sorted in advance merges more cheaply, and merging has no truly bad input.

Look at the level counters. The first level has eight merges of pairs, one comparison each: 8. After that merges get dearer, but a level still costs at most 16 comparisons: each comparison moves one element to the result, and a level has sixteen elements. With the input by date it came to 8 + 12 + 12 + 14 = 46. If the input is already sorted, each merge ends as soon as the left half runs out and makes as many comparisons as it has elements: 8 + 8 + 8 + 8 = 32.

Why n log n

Can one do better? Any sort that learns about the data only through comparisons makes at least log₂ n! ≈ n log₂ n − 1.44n comparisons in the worst case; why is told in the article on the lower bound. For sixteen elements that is 45, while the worst case of merging is 15 + 14 + 12 + 8 = 49: at each level each merge saves at least one comparison. In order of growth merging is optimal, and even the constant hardly differs from the best possible.

Code

In Python it is convenient to return a new list: the slices a[:mid] and a[mid:] copy the halves, and the merge assembles a third list. This is simple but spends memory at every level. In Go the buffer is allocated once for the whole sort: the merge writes into it, and then the result is copied back into the array. The counter counts collects comparisons by recursion level, the same numbers as in the scene.

And this is the first scene as a program: the catalogue on the server, three ways to split it into two feeds and the merge back into one chronicle.

What it costs

The time is Θ(n log n) on any input: even on a sorted array the merge makes about (n/2) log₂ n comparisons and honestly rewrites all the elements at every level. This is both a virtue and a drawback: there are no bad inputs, but almost-ready data gets sorted only a little faster than random. The memory is O(n) for the buffer plus O(log n) for the recursion. Two pieces can be merged in place, without a buffer, but it is harder and slower; sort.Stable in Go does this, for example, and its documentation honestly warns: O(n log n) comparisons but O(n log² n) swaps.

A measurement on random numbers, in Python and Go. For comparison, insertion sort from the article on simple sorts and the built-in sort.

Merging has a slope a little over one, which is how n log n looks on logarithmic axes; insertion about two. Already at a few hundred elements merging overtakes insertion, and after that the difference grows as n / log n. In Python the built-in sort beats our merge by more than twenty times: it is written in C and compares numbers without the interpreter. In Go a twenty-line merge keeps level with the standard slices.Sort: on a million numbers the difference is within a quarter.

On small pieces merging is hampered by overheads: a function call, slices, copying into the buffer. So real implementations take the recursion not down to one element but to pieces of a few dozen and sort those by insertion. How much this pays off is seen in the measurement: the same merge, but pieces no longer than a threshold are sorted by insertion.

The curve is a valley. On the left the recursion is too deep, on the right insertion on long pieces starts paying the square. At the bottom the gain is about 30% in Go and twofold in Python. In Python the bottom is around 16 elements, in Go around 64: each language has its own ratio between the price of a function call and the price of a shift. This is exactly why Timsort sorts short pieces by insertion, and sort.Stable in Go starts with insertion in blocks of 20 elements.

Stability for free

The rule “on a tie take from the left half” makes the sort stable at no cost. In the demo above, the magnitude 7.4 earthquakes come out sorted by date: 05-02, 07-20, 09-13, 10-10, just as they stood on input. So where stability is required, merging is usually what is used. Python promises stability for sorted and list.sort, and inside them is Timsort, a hybrid of merges and insertions. Java sorts arrays of objects with Timsort too, because the documentation promises stability, while arrays of numbers are sorted by a quicksort with two pivots: there is nothing to tell two equal numbers apart, and stability is not needed there.

When the data does not fit in memory

A merge reads each list in a row, from start to end, and writes the result in a row too. It needs no random access, and so files that do not fit in memory are sorted by merging. The scheme of external sorting is this: read the file in pieces the size of memory, sort each piece and write it to disk, giving sorted runs. Then merge the runs, many at once: a heap holds the first element of each run, as in the problem about regional catalogues.

A hundred gigabytes with four gigabytes of memory is 25 runs. Merged in pairs, they need ⌈log₂ 25⌉ = 5 passes over the whole file. Merged all 25 at once, one pass is enough, and the memory is divided among 25 read buffers of 160 megabytes.

The one in the brackets is the first pass, on which the runs are created. This is how GNU sort works: it sorts large inputs in pieces into temporary files and merges them, at most a given number of files at a time (the --batch-size option). Databases do the same: if the memory allotted is not enough for ORDER BY, PostgreSQL writes Sort Method: external merge in the query plan, with how much disk space was used.

The same sequence of actions works in memory too: merge neighbouring elements into pairs, pairs into fours and so on, without recursion. This is bottom-up merge sort, the tournament of the second scene read from top to bottom. And if instead of cutting the array blindly you take as runs the ordered pieces the data already contains, you get natural merge sort. Timsort is built on this idea: on almost sorted data there are few runs, and almost no merges.

The oldest program about sorting

In 1945 John von Neumann was working on the EDVAC project, one of the first machines to store its program in memory. The machine had not yet been built, but he was already writing a program for it, and he took the task of sorting: by hand, on 23 pages, he laid out the merging of two ordered sequences, the basis of merge sort. In 1970 Donald Knuth analysed this manuscript in the paper “Von Neumann’s first computer program” and called it the earliest surviving program for a stored-program machine.

While large data sets lived on magnetic tapes, merging remained the main way to sort them: a tape can only read in a row, and merging needs nothing more. A good part of the third volume of Knuth’s “The Art of Computer Programming” is devoted to exactly sorting on tapes: how many tapes, in what order to merge, how to distribute runs so that the tapes are not left idle.

Problems

In the first problem merge sort is needed not for the order but for the counter: along the way it counts the pairs that are out of place. In the second, merging many feeds at once.