How merge sort works
Why splitting a list down to single items and then stitching the pieces back together is one of the most dependable ways to put data in order.
Written by Amili, an AI writer, from the sources listed below · 17 October 2026 · 5 min read
Merge sort is a sorting method that breaks a list into tiny pieces, then combines them back in order, two sorted pieces at a time. It reliably takes O(n log n) comparisons even in its worst case, keeps equal items in their original order, and suits data read sequentially.
In short
- Merge sort splits a list until every piece holds one item, then merges the pieces back in order.
- Merging two lists that are already sorted only needs a single pass over both.
- Its worst case is O(n log n), the same order of work as its average case.
- It is usually stable, so equal items keep their starting order.
- The common array version needs extra memory roughly the size of the input.
How does merge sort work, step by step?
Merge sort rests on one small observation: a list containing a single item is already sorted. So the method starts by cutting the unsorted list in half, then cutting each half in half again, and so on, until nothing is left but one-item pieces.
Then it reverses direction. It takes two neighbouring pieces and merges them into one sorted piece. To merge, it looks at the front item of each piece, moves the smaller one into the result, and repeats. When one piece runs out, whatever remains in the other is copied across, because it is already in order. Merging keeps going, level by level, until a single sorted list remains.
John von Neumann came up with the method in 1945, and a written analysis of the bottom-up version appeared in a 1948 report by Goldstine and von Neumann. It is a classic example of divide and conquer: solve a big problem by solving smaller copies of it and combining the answers.
What does a worked example look like?
Imagine eight numbered cards: 6, 3, 8, 1, 7, 2, 5, 4. Splitting gives single cards. The first round of merging pairs them up: (3, 6), (1, 8), (2, 7), (4, 5).
The second round merges pairs into groups of four. Merging (3, 6) with (1, 8) compares 3 and 1 and takes 1, then compares 3 and 8 and takes 3, then 6, then 8, giving (1, 3, 6, 8). The other half becomes (2, 4, 5, 7).
The final merge combines those two groups into one fully ordered row, running from 1 up to 8. Each round touched every card once, and eight cards needed only three rounds, because halving eight three times reaches one. That is where the log n in its running time comes from: about log n levels, each doing roughly n steps of work.
A variation called natural merge sort skips the first split when the input already contains sorted stretches, called runs. If a list is already fully sorted, it is one run, and a single pass is enough. This idea is a key part of Timsort, a widely used sorting routine dating to 2002.
Where is merge sort used?
Because merge sort reads its input in order from front to back, it works well when data can only be read sequentially. That made it popular in Lisp, where linked lists are common, and it made it the natural choice for sorting data too large to fit in memory.
In the era of tape drives, a typical external sort used four tapes. Records were merged in pairs onto two tapes, then those pairs merged into fours onto the other two, back and forth, until one sorted list remained. Real systems usually began by sorting a large batch in memory first; sorting 1024 records in memory up front saves nine passes over the tapes.
On modern machines, cache-aware versions stop splitting once a piece fits in the processor's cache, sort it there with a simple method such as insertion sort, and then merge as normal. Merge sort also parallelises well, since its independent halves can be handled at the same time.
Where does merge sort fall short?
The main cost is memory. The usual array version does not sort in place, so it needs a second buffer about as large as the input. Variants exist that need only half that, and some library implementations cut the overhead to roughly the square root of n by using binary searches and rotations.
Fully in-place merge sorts have been designed, going back to Kronrod in 1969, but many are complicated, carry high constant factors, or give up stability. For data held in arrays in fast memory, quicksort is often slightly faster in practice, even though merge sort makes about 39% fewer comparisons in its worst case than quicksort does on average.
What does merge sort teach about thinking?
Merge sort shows the power of a guarantee. Its worst case and its average case are the same order of work, so its behaviour is predictable whatever input arrives. That predictability is often worth more than a small edge in typical speed.
It also shows how a problem that looks large can collapse into many trivial ones. Nobody needs to know how to sort a hundred items at once; it is enough to know that one item is sorted and that two sorted lists can be joined in a single pass.
Questions people ask
Is merge sort stable?
Most implementations are. A stable sort keeps items with equal keys in the order they had in the input. Merge sort achieves this by always taking from the left piece when the two front items are equal. Stability matters when data is sorted by several keys in turn, such as by name and then by class section, so the earlier ordering survives.
What is the time complexity of merge sort?
Merge sort takes O(n log n) comparisons in both the average and the worst case. Its running time follows the recurrence T(n) = 2T(n/2) + n: sort two halves, then spend about n steps merging them. Even its best case still needs roughly half the iterations of the worst, and it never degrades to the quadratic behaviour some other sorts can show.
Is merge sort better than quicksort?
It depends on the data and the constraints. Merge sort has a firm worst case, is stable, and suits sequential access such as linked lists or files on disk. Quicksort usually sorts in place with little extra memory and tends to run slightly faster on randomised data held in arrays, but its worst case is quadratic.
The thinking behind it
It introduces sorting and divide-and-conquer thinking with plain illustrations aimed at beginners.
Read or listen to Grokking Algorithms
Hear the whole book free: start an Audible trial and your first audiobook — this one, if you like — is on the house.
As an Amazon Associate, ReadGlobe earns from qualifying purchases and Audible trials — at no extra cost to you.
Sources
- Merge sort — Wikipedia
- Sorting algorithm — Wikipedia
- Dictionary of Algorithms and Data Structures — NIST
How this was made: Amili, an AI writer, wrote this article in its own words from the sources above. Every link was checked before publishing. Spotted an error? Tell us and we will correct it.