Merge sort

Merge sort turns one hard problem into many easy ones: two sorted lists are simple to combine into one. Split the list in half until every piece is a single value, then merge the pieces back together. It is the classic divide-and-conquer algorithm, and its time is n log n whatever the input.

Two sorted halves of a list lifted into a buffer row, and the smaller front value going back up into the list
Two sorted halves of a list lifted into a buffer row, and the smaller front value going back up into the list

The idea

Merging is the easy part. Given two lists that are each sorted, compare their first values and take the smaller one. Compare the new first values and take the smaller again. When one list runs out, append the rest of the other. Every step takes one value, so merging two lists of total length m takes at most m − 1 comparisons. Merge sort uses that to sort: split the list in half, sort each half with merge sort, and merge the two halves.

An example

Take 5, 1, 4, 2, 8. Split it into 5, 1 and 4, 2, 8. The first half splits into 5 and 1, which merge into 1, 5. The second half splits into 4 and 2, 8; the 2, 8 is merged from 2 and 8, then merged with 4 into 2, 4, 8. Finally 1, 5 and 2, 4, 8 merge: 1, then 2, then 4, then 5, and 8 is left over. That is 8 comparisons, 12 writes and 4 merges.

Why n log n

Each split halves the pieces, so after about log₂ n levels every piece is a single value. On the way back up, each level of merges handles every value once, which is n writes and fewer than n comparisons per level. In total that is about n log₂ n. For 40 values the sort makes 216 writes and at most 177 comparisons; bubble sort can need 780 comparisons for the same list. The order of the input matters much less than for those sorts: for 40 values, a sorted list takes 100 comparisons, a reversed one 116, and a random one about 160.

The buffer, and stability

To merge two halves that sit next to each other in the list, the usual method copies them out to a buffer and writes them back in order. The app shows that buffer as the second row of bars. It needs as much extra memory as the list, which is merge sort's main cost. In return the sort is stable: when the two front values are equal, the one from the left half goes first, so equal values keep their order. Stability matters when sorting records by one field after another.

History and use

John von Neumann described merge sort in 1945, which makes it one of the first algorithms written for a stored-program computer. Because it reads and writes data in long runs, it was the standard method for sorting data on tape and is still used for files too large for memory. Timsort, used by Python and by Java for objects, is a merge sort that first finds runs that are already sorted and uses insertion sort for short pieces.

John von Neumann, in his Los Alamos badge photograph. He described merge sort in 1945, one of the first algorithms written for a stored-program computer.
John von Neumann, in his Los Alamos badge photograph. He described merge sort in 1945, one of the first algorithms written for a stored-program computer.

Explore it

Open the app and press Step. The shaded part of the list is being split or merged, and the dashed line marks the middle. When a merge starts, both halves drop into the buffer row; the two front values are compared, and the smaller goes back up. Watch the counters: the writes are the same for every list of the same length, and the comparisons are lowest for a sorted or reversed list and highest for a random one, but never more than about n log₂ n.

Frequently asked questions

What is the time complexity of merge sort?

O(n log n) in the best, average and worst case. The usual version needs O(n) extra memory for the buffer.

What is the difference between merge sort and quicksort?

Both divide the list and sort the parts. Merge sort splits at the middle without looking at the values and does its work when merging; quicksort does its work when splitting, by moving values around a pivot, and needs no merge. Quicksort sorts in place and is often faster in practice, but it can slow to n² on bad inputs and is not stable. Merge sort is always n log n and stable.

What is bottom-up merge sort?

A version without recursion: first merge neighbouring single values into pairs, then pairs into fours, and so on, doubling the length each round. It does the same work as the top-down version shown here.

Is merge sort stable?

Yes, as long as a tie takes the value from the left half first, as this app does.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Try merge sort