How Merge Sort Works
Merge sort is two ideas glued together: splitting a problem until it is trivial, and merging two sorted lists in one pass. The recursion is easy to accept and hard to picture, because nothing interesting happens on the way down — all the actual sorting occurs during the unwind, which is exactly the part a static diagram cannot show you.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
void merge(vector<int>& a, int lo, int mid, int hi) {
vector<int> tmp;
int i = lo, j = mid + 1;
while (i <= mid && j <= hi) {
if (a[i] <= a[j]) tmp.push_back(a[i++]);
else tmp.push_back(a[j++]);
}
while (i <= mid) tmp.push_back(a[i++]);
while (j <= hi) tmp.push_back(a[j++]);
for (int k = 0; k < (int)tmp.size(); k++) a[lo + k] = tmp[k];
}
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);
merge(a, lo, mid, hi);
}
int main() {
vector<int> a = {38, 27, 43, 3, 9, 82, 10};
mergeSort(a, 0, (int)a.size() - 1);
for (int x : a) cout << x << ' ';
return 0;
}Top-down merge sort with inclusive bounds; merge builds the combined run in a temporary vector and copies it back over the original range.
How it works, step by step
The descent does nothing but split
Every call halves its range and recurses. No comparison happens until a range shrinks to one element, at which point lo >= hi and the call returns immediately. Watching the call stack grow to depth log n before a single value moves is the moment merge sort clicks for most people.
Merging is a two-finger scan
i walks the left half, j walks the right, and each step takes whichever front element is smaller. Because both halves are already sorted, the smaller of the two fronts is the smallest element remaining anywhere — that single fact makes the merge linear instead of quadratic.
The drain loops handle the leftover
One half runs out first. The two trailing while loops copy whatever remains from the other half; it is already sorted and already larger than everything placed so far, so it can be appended wholesale.
Copying back is what makes it in-place-ish
The merge builds its result in tmp and then overwrites a[lo..hi]. The array itself is always the source of truth, so the parent call sees a correctly sorted subrange without knowing anything about how it was produced.
log n levels, n work per level
Halving reaches single elements after log2(n) levels. At every level the merges collectively touch each element exactly once. Multiply and you get n log n, and unlike quicksort there is no input that breaks it.
Complexity
The recursion depth is log n and each level merges every element once, with no dependence on input order; the O(n) space is the temporary buffer, which is the real cost and the reason quicksort is often preferred in memory-constrained code.
Common bugs
Using lo > hi instead of lo >= hi as the base case
With lo > hi, a single-element range keeps recursing: mid equals lo, the left call gets the identical range, and you get infinite recursion into a stack overflow. In DryRun the call stack shows the same (lo, hi) pair on frame after frame until it runs out of room, which is the whole diagnosis in one screen.
Splitting into (lo, mid) and (mid, hi)
The right half must start at mid + 1. Passing mid means the element at mid appears in both halves, so it gets duplicated and something else gets lost, and if the range has two elements the right call never shrinks and recursion never ends. The merge call must use the same mid the split used.
Copying back to a[k] instead of a[lo + k]
tmp is indexed from 0 but the range starts at lo. Writing a[k] = tmp[k] sorts the subrange into the front of the array instead of back where it came from, scrambling everything. It looks correct for the leftmost branch — which is the one people usually trace by hand — and wrong everywhere else.
Using < instead of <= when comparing the two fronts
if (a[i] < a[j]) takes from the right half when the values are equal, which reverses the original order of equal elements and makes the sort unstable. Merge sort's stability is the main reason to choose it over quicksort, and this one character throws it away.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
Why is merge sort O(n log n) in every case?
Because the split is positional, not value-based: the range is always halved down the middle regardless of what the data contains. That fixes the recursion depth at log2(n), and each level does exactly n work merging. No input can unbalance it, which is the guarantee quicksort cannot make.
Why does merge sort need extra memory?
The merge step reads from two sorted runs and writes a combined run, and it cannot write into the array it is still reading without overwriting values it needs. The standard fix is an O(n) temporary buffer. In-place merge algorithms exist but are substantially slower and far more intricate.
Is merge sort better than quick sort?
It depends on what you need. Merge sort guarantees O(n log n) and is stable, which makes it the right choice for linked lists, external sorting, and when equal elements must keep their order. Quicksort is typically faster in practice on arrays because it sorts in place with better cache behaviour, at the cost of an O(n squared) worst case.
Where does the actual sorting happen in merge sort?
Entirely in the merge step, on the way back up the recursion. The downward phase only computes midpoints and makes calls — no element moves until a call returns and its parent merges two now-sorted halves. That is why the array looks completely untouched for the first log n steps of a trace.