Merge sort is a comparison-based sorting algorithm that recursively splits a sequence into halves, sorts each half and merges the sorted halves into one ordered result. Within the study of algorithms it is the classic example of the divide and conquer strategy, and in everyday programming it is valued because it guarantees O(n log n) time in every case and is stable, meaning equal elements keep their original order.
The algorithm is usually attributed to John von Neumann in 1945. Its predictable performance and suitability for sequential data access explain why variants of merge sort sit at the core of standard library sorts and of external sorting for data too large for memory.
How merge sort divides and merges
Merge sort works in two phases: division and merging. The division phase splits the input repeatedly until each piece holds one element, which is sorted by definition. The merging phase then combines pairs of sorted pieces into larger sorted pieces until one sequence remains.
The merge step is where the work happens. Two pointers walk through the two sorted halves, the smaller current element is copied to an output buffer, and the pointer advances. When one half is exhausted, the rest of the other half is copied. Merging two runs of total length n takes at most n minus 1 comparisons. Choosing the left element when two keys are equal is what makes the algorithm stable.
The table below traces the process on a small input of eight numbers.
| Stage | State of the data |
|---|---|
| Input | 38, 27, 43, 3, 9, 82, 10, 5 |
| After splitting | Eight single-element runs |
| Merge into pairs | 27 38 | 3 43 | 9 82 | 5 10 |
| Merge into fours | 3 27 38 43 | 5 9 10 82 |
| Final merge | 3, 5, 9, 10, 27, 38, 43, 82 |
Time and space complexity of merge sort
The running time follows the recurrence T(n) = 2T(n/2) + O(n). The input is halved about log2 n times, and each level of recursion performs linear merging work, which gives O(n log n) comparisons regardless of how the input is arranged. Sorting one million elements therefore needs roughly 20 levels of merging.
| Measure | Value | Comment |
|---|---|---|
| Best case time | O(n log n) | O(n) with a natural-run check |
| Average case time | O(n log n) | Independent of input order |
| Worst case time | O(n log n) | No degenerate inputs |
| Auxiliary space | O(n) for arrays | Buffer for merging |
| Recursion depth | O(log n) | Small stack usage |
| Stability | Stable | Equal keys keep their order |
The main cost is space complexity. A typical array implementation allocates a buffer of n elements, so sorting a gigabyte of data in memory needs another gigabyte. In-place merge sort variants exist, but they are complex and noticeably slower in practice. On linked lists, merging only relinks nodes, so merge sort needs only O(log n) extra space or even constant space in a bottom-up form.
Merge sort compared with other sorting algorithms
Merge sort is most often weighed against quicksort and heapsort, the other two general-purpose O(n log n) comparison sorts. Each makes a different trade-off between guaranteed speed, memory use and stability.
| Algorithm | Worst case | Extra space | Stable | Practical strength |
|---|---|---|---|---|
| Merge sort | O(n log n) | O(n) | Yes | Predictable, sequential access |
| Quicksort | O(n²) | O(log n) | No | Fastest average on arrays |
| Heapsort | O(n log n) | O(1) | No | Guaranteed time without extra memory |
| Insertion sort | O(n²) | O(1) | Yes | Very fast on small or nearly sorted data |
| Bubble sort | O(n²) | O(1) | Yes | Teaching only |
Quicksort usually wins on in-memory arrays because it works in place and uses the CPU cache well, but it degrades to quadratic time with poor pivot choices. Merge sort gives up memory to remove that risk. Timsort, used by Python and by Java for object arrays, combines merge sort with insertion sort and detects already sorted runs, which makes it very fast on real-world data.
Variants and practical implementation choices
Production implementations rarely use the textbook version unchanged. Several well-established refinements reduce overhead while keeping the guarantees.
| Variant | Key idea | When it helps |
|---|---|---|
| Top-down | Recursive halving | Clear code, teaching |
| Bottom-up | Iteratively merge runs of 1, 2, 4 and more | Avoids recursion, linked lists |
| Natural merge sort | Merge existing sorted runs | Partially sorted input |
| External merge sort | Sort chunks in memory, merge files | Data larger than RAM |
| Parallel merge sort | Sort halves on separate cores | Multicore systems |
Two refinements appear in almost every serious implementation: switching to insertion sort for small subarrays, typically below 16 to 64 elements, and skipping the merge when the last element of the left half is already smaller than the first element of the right half. Reusing a single preallocated buffer instead of allocating one per call also removes significant overhead.
Common mistakes when implementing merge sort
Merge sort is conceptually simple, yet implementation errors are frequent, especially in interviews and hand-written utilities.
- Breaking stability by taking the right element when keys are equal.
- Allocating new arrays in every recursive call, which multiplies memory traffic.
- Integer overflow in the midpoint, where (low + high) / 2 should be low + (high – low) / 2 in fixed-width languages.
- Off-by-one errors in inclusive and exclusive bounds that drop or duplicate elements.
- Using merge sort on tiny arrays where insertion sort is faster.
The short version
Imagine sorting a large stack of exam papers by name. You split the stack in half, then split each half again, until every pile holds one paper. Then you combine piles two at a time, always taking the paper that comes first alphabetically.
Combining two already sorted piles is quick and easy. Merge sort is fast and reliable because it only ever merges sorted piles. It also keeps papers with the same name in their original order.
Where it makes a difference
A logistics company must sort a 200 GB file of shipment records by date on a server with only 16 GB of RAM. Loading the file into memory is impossible, so the engineers use an external merge sort.
The program reads the file in chunks of about 4 GB, sorts each chunk in memory and writes it back as a sorted run, producing about 50 runs. A final pass then merges all runs at once using a small priority queue, reading each run sequentially. Because disks handle sequential reads efficiently, the job finishes in a predictable time, and records with the same date keep their original order, which downstream reports depend on.