Merge Sort

Split the array in half, sort each half, merge the two sorted halves. Always O(n log n), stable, and the merge step can count cross pairs, sort a linked list, or sort data that does not fit in memory.

Overview

The idea

Merge sort splits the array in half, sorts each half by the same method, and merges the two sorted halves into one. A single value is already sorted, which is the base case. John von Neumann described the method in 1945.

Time — O(n log n) in the best, average and worst case — every level of merging does n work, and there are log2 n levels
Extra space — O(n) for arrays, O(1) beyond the stack for linked lists — the merge writes into a buffer; on a list it relinks nodes
Stable — yes, when a tie takes from the left half — equal values keep their input order
Access pattern — sequential — it never jumps around, so it suits lists, disks and tapes

Quicksort is usually faster on arrays in memory, but it has an O(n²) worst case and is not stable. Merge sort is the answer when you need a guaranteed bound, stability, a linked list, or data larger than memory.

The merge step

Two sorted halves become one sorted array by looking at the front of each half and taking the smaller value. On a tie, take from the left half: that is what makes the sort stable.

The trace below merges [2, 4, 5, 7] with [1, 2, 3, 6].

1 — 2 — 1 — 1 from the right — 1
2 — 2 — 2 — 2 from the left (tie) — 1 2
3 — 4 — 2 — 2 from the right — 1 2 2
4 — 4 — 3 — 3 from the right — 1 2 2 3
5 — 4 — 6 — 4 from the left — 1 2 2 3 4
6 — 5 — 6 — 5 from the left — 1 2 2 3 4 5
7 — 7 — 6 — 6 from the right — 1 2 2 3 4 5 6
8 — 7 — empty — copy the rest — 1 2 2 3 4 5 6 7

The classic bug is forgetting step 8. When one half runs out, the rest of the other half still has to be copied.

Why it is always O(n log n)

Sorting [5, 2, 4, 7, 1, 3, 2, 6] splits three times. At every level the pieces together hold all eight values, and merging a level costs one pass over them.

3 — 5, 2, 4, 7, 1, 3, 2, 6 — base cases
2 — 2 5, 4 7, 1 3, 2 6 — 8
1 — 2 4 5 7, 1 2 3 6 — 8
0 — 1 2 2 3 4 5 6 7 — 8

The split is always exactly in half, so nothing about the input can make the tree deeper. That is the difference from quicksort, whose depth depends on the pivots. For n = 1,000,000 the tree has about 20 levels, so the sort moves about 20 million values.

The cost is the buffer. Allocate one array of size n once and reuse it for every merge; allocating a new list in every call still works but adds time and memory. The call stack is only O(log n) deep.

Bottom-up merge sort

The same merges can run without recursion. Treat each value as a sorted run of width 1, merge neighbors into runs of width 2, then 4, and so on until one run remains.

start — 1 — 5 2 4 7 1 3 2 6
1 — 2 — 2 5 4 7 1 3 2 6
2 — 4 — 2 4 5 7 1 2 3 6
3 — 8 — 1 2 2 3 4 5 6 7

Bottom-up is the form used for linked lists when O(1) extra space is required, and it is the shape of the merge phase in external sorting.

Sorting a linked list

Sort List is the problem where merge sort is the expected answer. A list has no random access, so quicksort and heapsort do not fit, but merge sort only ever walks forward.

Find the middle — slow and fast pointers; stop on the first middle — O(n)
Cut — set middle.next to null — O(1)
Sort both halves — recursion — 2T(n/2)
Merge — relink nodes behind a dummy head; no new nodes — O(n)

The time is O(n log n). Only pointers change, so the extra space is the O(log n) stack, or O(1) with the bottom-up form. Forgetting to cut the list is the usual bug: the left half then still runs into the right half and the recursion never ends.

Counting while merging

The merge sees every pair that crosses the middle, in sorted order, so it can count them without extra passes.

Inversions are pairs with i a[j]. When the right front is taken while values still wait on the left, it is smaller than all of them, so add the number waiting. Merging [2, 4, 5, 7] with [1, 2, 3, 6] finds 4 + 3 + 3 + 1 = 11 cross inversions; with the 3 found inside the halves, the array [5, 2, 4, 7, 1, 3, 2, 6] has 14.

Reverse Pairs asks for pairs with i 2 times a[j]. The condition is not the sort order, so the merge comparison cannot count it. Run a separate two-pointer pass over the two sorted halves first: for each left value, advance a pointer on the right while the condition holds; the pointer never moves back, so the pass is O(n). Then merge as usual.

2 — none — 0
4 — 1 — 1

That is the final step for [2, 4, 3, 5, 1], split into [2, 4] and [3, 5, 1]. The left half had no pair and the right half had two, 3 with 1 and 5 with 1, so the answer is 3. Count of Smaller Numbers After Self is the same idea with the count kept per element.

When the data does not fit in memory

External merge sort has two phases. It reads the input in chunks that fit in memory, sorts each chunk and writes it out as a sorted run. Then it merges the runs with a k-way merge, taking the smallest front value with a min-heap of size k. Each phase streams the data sequentially, which is what disks are good at.

Make runs — one pass over the data — one chunk
Merge runs — one pass per merge round — one buffer per run plus the heap

Merge sort is also what the standard libraries build their stable sorts on. Python's sort is Timsort, a merge sort that first finds runs already in order, and it is guaranteed stable. Java's Arrays.sort on object arrays is a stable, adaptive, iterative merge sort adapted from Timsort; on primitive arrays Java uses a dual-pivot quicksort, since stability means nothing for equal ints. JavaScript's Array.prototype.sort has been required to be stable since ES2019; the language names no algorithm, and V8 uses Timsort.

What you will be able to do

Write the merge step without the missing-tail bug, and say why it makes the sort stable.
Explain why the cost is O(n log n) for every input, and what the O(n) buffer costs.
Sort a linked list in place with the slow and fast pointer cut.
Adapt the merge to count inversions and reverse pairs.
Describe external sorting and name what your language's stable sort is built on.

When to use it

A guaranteed O(n log n) worst case, where quicksort could hit O(n²)
Sorting a linked list, where only forward access is available
A stable sort, so equal keys keep their input order
Counting pairs that cross the middle: inversions, reverse pairs, smaller numbers after self
Sorting data larger than memory, as runs on disk merged in rounds

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio