What is merge sort?
Merge sort sorts by splitting an array in half, over and over, until every piece is down to a single element — and a single element is already sorted, trivially. Then it walks back up, merging pairs of already-sorted pieces into bigger sorted pieces, until one sorted array is left. Every merge step is a two pointer walk: compare the front of each piece and take the smaller one.
- Divide
- Split the array in half, recursively, until each piece is a single element
- Merge
- Walk two sorted pieces with two pointers, always taking the smaller front value
- Auxiliary array
- A separate array used to hold the merged result — merge sort doesn't sort in place
Why merge sort at all?
Picture two people splitting a deck of cards in half, each sorting their own half by hand. Once both halves are sorted, they combine them into one pile by always taking whichever top card is smaller.
Neither of them ever needs to look at the whole deck at once — sorting a half is easier than sorting the whole thing, and combining two already-sorted piles only takes one pass, comparing fronts.
Smaller front card goes down. Only that pile's pointer moves.
What kinds of problems does it solve?
Four common shapes. They all lean on the same two moves — split until trivial, then merge two sorted pieces with a two pointer walk.
Split until it's trivial
Cut the array in half, then cut each half in half, and so on. A piece of size 1 needs no work — it's already sorted. There's no comparison to make yet, only splitting.
Every split halves the work. Stop when a piece is one element.
Merge two sorted runs
This is the same technique as merging two sorted lists elsewhere on this site — one pointer per piece, always advance whichever pointer sits on the smaller value. That's the only real work merge sort does; everything else is just splitting and recombining.
Smaller front wins. Only that pointer moves — the other run's progress stays put.
Count inversions while merging
An inversion is a pair that's out of order. Every time the merge takes from the right run while the left run still has values left, every remaining left value is out of order with that one — so add the count of what's left in the left run, all at once, instead of checking pairs one by one.
Taking from the right early means every remaining left value is out of order with it.
Sort a linked list
Merge sort doesn't need random access to split or merge, only "what's next" — which is exactly what a linked list gives you. Find the middle node, sort each half, then merge two sorted lists by relinking nodes instead of writing into an array.
Same merge, one node at a time — only the pointers move, nothing is copied.
Two phases
Every merge sort call does one of two things: split the problem in half, or merge two already-sorted halves back together. Divide does no comparisons at all — merge does all of them.
Divide
Keep halving until arr.length <= 1. That's the base case — a single element needs no sorting.
Each recursive call gets smaller, so the splitting bottoms out after about log₂ n levels.
No comparisons yet — just splitting the problem down to nothing.
function mergeSort(arr: number[]): number[] {
if (arr.length <= 1) return arr; // base case: trivially sorted
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
Merge
Walk both sorted halves with two pointers. At each step, take whichever front value is smaller and advance only that pointer. This is where all the real work — every comparison — happens.
One pass, front to back — that's the O(n) part of every merge step.
function merge(left: number[], right: number[]): number[] {
const result: number[] = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) result.push(left[i++]);
else result.push(right[j++]);
}
// one side still has leftovers once the other runs out
return result.concat(left.slice(i), right.slice(j));
}
What it guarantees — and what it costs
Merge sort always does the same amount of work no matter how the input starts out. That guarantee isn't free — it comes from copying values into a second array instead of sorting in place.
Guaranteed O(n log n)
Splitting always takes log₂ n levels, and every level does one O(n) merge pass — that total
never changes, whether the array arrives sorted, reversed, or random. Quicksort is faster on average
but can degrade to O(n²) on the wrong input; merge sort never does.
Costs O(n) extra space
The merge step writes into a new array — it can't safely overwrite either half mid-comparison without losing a value it hasn't read yet. That auxiliary array is why merge sort isn't in place, unlike quicksort or insertion sort.