Merge sort
mediumNothing happens on the way down - all the work is in the merges on the way up. O(n log n) in every case including adversarial input, which is a guarantee quicksort cannot make.
O(n log n)Average O(n log n)Worst O(n log n)Space O(n)StableNeeds extra memorySaved in this browser - no sign-up, nothing sent anywhere.
How merge sort works
Split the array in half, sort each half, merge the two sorted halves - and sorting each half is the same problem, so recurse until slices hold one element, which is sorted by definition. This module is the top-down variant: mergeSort(a, lo, hi) splits at mid, recurses left then right, and merges through a buffer. Nothing is compared on the way down; every comparison lives in the merges on the way up.
Each merge is a two-finger walk: copy a[lo..hi] into a buffer, point one finger at each run's head, repeatedly write the smaller head back into the array. Ties take the left head - buf[i] <= buf[j] - and that one character is what makes the sort stable. Merging m elements never costs more than m - 1 comparisons.
The payoff is the guarantee: log n levels of halving, O(n) merge work per level, O(n log n) in every case - sorted, reversed, adversarial, no exceptions. 16 elements finish near the 64-comparison lower bound for comparison sorting. The price is the O(n) buffer. Reach for it when worst-case latency or stability is non-negotiable, or when the data is a linked list or does not fit in memory.
Step by step
- Sort [6, 3, 8, 2]. The recursion splits it into [6, 3] and [8, 2] before any comparison happens.
- [6, 3] splits into single elements, then merges: 6 versus 3 takes 3 first, giving [3, 6].
- [8, 2] does the same and becomes [2, 8]. The array now holds two sorted runs: [3, 6, 2, 8].
- The final merge copies both runs to the buffer and compares heads: 3 versus 2 takes 2, then 3 versus 8 takes 3.
- 6 versus 8 takes 6, the left run empties, and the leftover 8 is copied across without a comparison.
- Result [2, 3, 6, 8] in 5 comparisons total - and every input ordering of these four values would cost about the same.
Complexity
| Best case time | O(n log n) |
|---|---|
| Average time | O(n log n) |
| Worst case time | O(n log n) |
| Space | O(n) |
log n levels of recursion, each doing O(n) merging work.
Reference implementation
Python
def merge_sort(a, lo=0, hi=None):
if hi is None:
hi = len(a) - 1
if lo >= hi:
return a
mid = (lo + hi) // 2
merge_sort(a, lo, mid)
merge_sort(a, mid + 1, hi)
buf = a[lo:hi + 1]
i, j, k = 0, mid - lo + 1, lo
while i <= mid - lo and j < len(buf):
if buf[i] <= buf[j]: # <= keeps the sort stable
a[k] = buf[i]; i += 1
else:
a[k] = buf[j]; j += 1
k += 1
while i <= mid - lo:
a[k] = buf[i]; i += 1; k += 1
while j < len(buf):
a[k] = buf[j]; j += 1; k += 1
return aJavaScript
function mergeSort(a, lo = 0, hi = a.length - 1) {
if (lo >= hi) return a;
const mid = (lo + hi) >> 1;
mergeSort(a, lo, mid);
mergeSort(a, mid + 1, hi);
const buf = a.slice(lo, hi + 1);
let i = 0, j = mid - lo + 1, k = lo;
while (i <= mid - lo && j < buf.length) {
a[k++] = buf[i] <= buf[j] ? buf[i++] : buf[j++]; // <= keeps it stable
}
while (i <= mid - lo) a[k++] = buf[i++];
while (j < buf.length) a[k++] = buf[j++];
return a;
}Java
static void mergeSort(int[] a, int lo, int hi) {
if (lo >= hi) return;
int mid = (lo + hi) >>> 1;
mergeSort(a, lo, mid);
mergeSort(a, mid + 1, hi);
int[] buf = Arrays.copyOfRange(a, lo, hi + 1);
int i = 0, j = mid - lo + 1, k = lo;
while (i <= mid - lo && j < buf.length)
a[k++] = (buf[i] <= buf[j]) ? buf[i++] : buf[j++];
while (i <= mid - lo) a[k++] = buf[i++];
while (j < buf.length) a[k++] = buf[j++];
}C++
void mergeSort(vector<int>& a, int lo, int hi) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
mergeSort(a, lo, mid);
mergeSort(a, mid + 1, hi);
vector<int> buf(a.begin() + lo, a.begin() + hi + 1);
int i = 0, j = mid - lo + 1, k = lo;
while (i <= mid - lo && j < (int)buf.size())
a[k++] = (buf[i] <= buf[j]) ? buf[i++] : buf[j++];
while (i <= mid - lo) a[k++] = buf[i++];
while (j < (int)buf.size()) a[k++] = buf[j++];
}Worth noticing
Nothing happens on the way down
Watch the call stack: the recursion splits all the way to single elements before a single comparison happens. All the work is in the merges on the way back up, which is why the shape of the input barely changes the running time.
Every merge is a two-finger walk
Two sorted runs, one pointer in each, always take the smaller head. That is the entire merge step - and it is why merging two sorted lists of total length m costs exactly m comparisons at most.
The `<=` is what makes it stable
When the two heads are equal, taking from the left run first preserves the original relative order. Flip it to `<` and merge sort quietly becomes unstable - the classic interview trap.
You pay O(n) memory for the guarantee
The buffer row shows the copy each merge needs. In exchange you get O(n log n) in every case, including adversarial input - which quicksort cannot promise.
Common pitfalls
- Writing < instead of <= when the two heads tie. The output is still sorted, but equal elements cross runs out of order - the classic silent stability bug.
- Forgetting the leftover-copy loops after one run empties. The tail of the other run never lands, and the bug only shows on inputs where one side drains early.
- Merging in place without the buffer - the write position overruns unread elements of the left run. The copy is not an optimization detail; it is correctness.
- Allocating a fresh buffer inside every merge call in production code. This visualizer does it for clarity, but real implementations allocate one n-sized scratch array once.
- Computing mid as (lo + hi) / 2 in fixed-width languages - the same overflow as binary search. The Java sample here uses >>> 1 and the C++ sample uses lo + (hi - lo) / 2 for exactly that reason.
Where it is used
- Timsort - Python's sorted and Java's object Arrays.sort - is merge sort tuned to exploit existing runs, kept because stability is part of Java's contract.
- External sorting: database ORDER BY and Unix sort merge sorted runs that never fit in RAM together.
- Linked lists, where merging is pointer surgery with O(1) extra space and no random access is ever needed.
- Counting inversions - the standard interview extension that piggybacks a counter on the merge step.
Frequently asked questions
What is the time and space complexity of merge sort?
O(n log n) in the best, average, and worst case - log n levels of recursion, each doing O(n) merge work, with no input that changes the shape. Space is O(n) for the merge buffer plus O(log n) of recursion stack, which is why it is not in place.
Why is merge sort stable?
One comparison makes it so: when the two run heads are equal, buf[i] <= buf[j] takes from the left run first, and the left run holds the elements that came earlier in the original array. Equal values therefore never cross. Flip the comparison to strict < and stability silently disappears.
Is merge sort better than quicksort?
It depends what you are buying. Merge sort guarantees O(n log n) on every input and keeps equal elements in order; quicksort risks O(n²) and is unstable, but sorts in place with better cache behaviour and usually wins on wall-clock time. Libraries split the difference: stable sorts get merge sort variants, unstable ones get quicksort variants.
Can merge sort run without the O(n) extra memory?
Not practically for arrays. In-place merging exists but is complicated and slow enough that nobody ships it as a default; the standard answer is to accept one n-sized buffer allocated once. Linked lists are the real exception - merging relinks nodes, so list merge sort runs in O(1) extra space.