Merge sort takes the opposite bet from insertion sort: instead of growing one sorted region by shifting elements into place, it splits the array into halves, sorts each half independently, and then merges the two sorted halves back together in one linear pass. The merge is the whole trick — given two already-sorted lists, you can produce one sorted list by repeatedly taking the smaller of the two fronts, which takes time proportional to their combined length, no comparisons wasted.
Enter a comma-separated list of numbers, then step through the sort. The dashed box is the active window being merged, split into a left half and a right half (shaded differently); the two highlighted bars are the elements currently being compared. Once a window finishes merging it settles into place and the next, larger window takes over.
The invariant is on the window, not the whole array: a window of size 1 is trivially
sorted. Merging two sorted windows of size w produces one sorted window of size
2w. The demo above sorts this way — bottom-up, doubling the window size each pass
(1, then 2, then 4, ...) — rather than the more commonly taught top-down recursive version,
because it steps predictably without needing to track a call stack in the visualizer. Both
produce identical results; they're the same algorithm viewed from opposite ends.
The canonical, recursive top-down version — split until you hit single elements, then merge on the way back up:
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const out = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) out.push(left[i++]);
else out.push(right[j++]);
}
while (i < left.length) out.push(left[i++]);
while (j < right.length) out.push(right[j++]);
return out;
}It's not in-place. Each merge needs somewhere to build its result before
copying it back — the recursive version above allocates a new array at every level, and even
a careful in-place merge implementation needs O(n) auxiliary space at minimum. This
is the direct trade for merge sort's guaranteed O(n log n): insertion sort sorts in
O(1) extra space but degrades to O(n²).
Stability, and why <= matters. The merge step takes from the
left when the two fronts are equal (left[i] <= right[j]), which keeps elements
from the left half ahead of equal elements from the right half — exactly their original relative
order, since the left half started to the left of the right half. Flip it to strict
< and the sort still produces correct output, but stability breaks, the same
subtlety as insertion sort's > versus >=.
No best case. Insertion sort runs in O(n) on already-sorted
input because its inner loop can bail out early. Merge sort has no equivalent shortcut — it
always splits all the way down and merges all the way back up, so best, average, and worst case
are all O(n log n). Predictable, but it can't out-run insertion sort on small or
nearly-sorted inputs.
Time: O(n log n) in every case — log n levels of
splitting, each level doing O(n) total work across all its merges.
Space: O(n) extra for the merge buffers. That guaranteed
n log n bound, plus stability, is why merge sort (or a hybrid built on it, like
Timsort) backs the stable sort in most standard
libraries — Python's list.sort,
Java's Arrays.sort for objects, and array merges are the O(log n) backbone behind
external sorting, where the data doesn't fit in memory and you're merging pre-sorted chunks read
from disk.
For the other classic divide-and-conquer sort, see quicksort — same average-case O(n log n), but
it partitions in place instead of merging into buffers, trading merge sort's guaranteed bound for
a smaller memory footprint and a worst case that shows up on already-sorted input.
That n log n bound is actually a theorem about a specific kind of sort —
one that only ever asks "is A bigger than B?" Merge sort, insertion sort, quicksort, and
heap sort are all built entirely out of such comparisons,
so none of them can beat it. Counting sort escapes the
bound instead of beating it, by never comparing elements at all — worth reading once this page's
guarantee starts to feel like a hard floor rather than one strategy's tradeoff.
See Choosing a Comparison Sort for how merge sort's stability and guaranteed bound stack up against the other ten comparison sorts on this site.