Merge sort is a divide-and-conquer sorting algorithm. It splits the array in half repeatedly until each piece is a single element (already sorted), then merges neighbouring pieces back together in order. Because merging two sorted lists is linear, and there are about log n levels of merging, it always runs in O(n log n) time.

Merge sort vs quicksort — which is better?

Quicksort sorts in place (O(log n) extra memory) and is usually faster in practice thanks to cache locality, but it has an O(n²) worst case and is not stable. Merge sort guarantees O(n log n) on every input and is stable, but needs O(n) extra memory. Use quicksort for in-memory arrays; merge sort for linked lists, external/disk sorting, and when a guaranteed bound or stability is required.

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

ALGORITHMS · 04 / MERGE SORT

The Cascade.

Watch the explainer

Split until every piece is one element — already sorted — then merge them back, two sorted runs at a time, all the way up. The reward: O(n log n) on every input, no meltdown.

THE GIST · 20 SECONDS

Merge sort splits the array in half again and again until each piece is a single element (trivially sorted), then merges neighbouring pieces back in order. Merging two sorted runs is linear, and there are only ~log n levels of merging — so it always runs in O(n log n), no matter the input. The cost is O(n) extra memory.

Runa stretch that's already sorted
Mergefuse two sorted runs into one
Dividehalve until runs of size 1
Stableequal elements keep their order

① Watch runs cascade up → ② Merge two runs by hand → ③ Prove the guarantee

left run right run merged / sorted

A merge walks both sorted runs with one finger each and always copies the smaller front element next — that one linear pass is the whole trick.

UNDER THE HOOD

What you just played, written down

You watched runs cascade upward and merged two by hand. Here's the same thing as code.

How the Weaver thinks — the loop

Divide. Split the array in half, and each half in half, until every piece holds one element.
A single element is sorted. That's the base case — nothing to do.
Merge. Combine two sorted runs by repeatedly taking the smaller of their two front elements.
Climb. Keep merging neighbouring runs into bigger ones until a single sorted array remains.

WHY IT'S ALWAYS n log n

There are log₂(n) levels of merging, and each level merges every element exactly once — O(n) work. No input can change that count, so there is no worst case.

The algorithm

function mergeSort(a):
    if a.length <= 1: return a       # already sorted
    mid = a.length / 2
    left  = mergeSort(a[0 .. mid])
    right = mergeSort(a[mid .. end])
    return merge(left, right)

function merge(L, R):
    out = []; i = 0; j = 0
    while i < L.length and j < R.length:
        if L[i] <= R[j]:             # <= keeps it stable
            out.push(L[i]); i++
        else:
            out.push(R[j]); j++
    return out + L[i..] + R[j..]      # drain leftovers

TIMEO(n log n)best = worst = average

SPACEO(n)temporary merge buffer · stable

⌁ The cascade you played is the bottom-up view — it fuses the smallest runs first. The code above is the top-down recursion, but it performs the exact same merges, just discovered from the inside out. Same work, two ways to write it.

Solved by hand — the merge passes for the array above

Each bottom-up pass, the run size it produced, and the runs it fused.

↔ Merge sort vs quicksort

Merge sort: guaranteed O(n log n), stable — but O(n) extra memory. Quicksort: in place and cache-friendly, usually faster — but O(n²) worst case and unstable.

⚠ The memory cost

The linear merge needs a temporary buffer the size of the data. On huge arrays that O(n) memory is the real trade-off you pay for the guaranteed time.

★ Where it's used

External sorting of disk-sized data, sorting linked lists, and stable library sorts (Python's Timsort, Java's object sort) are merge-sort hybrids.

The picture: split down, merge up

The code’s input, [5, 2, 9, 1, 5, 6]. The top half only divides; nothing is compared until the pieces start coming back up. Sorting this array takes 10 comparisons, and the result is 1, 2, 5, 5, 6, 9. The same merges, counted differently, also give the number of inversions (pairs out of order): 6 here, each time a right-run element jumps ahead of the left-run elements still waiting.

Complexity and trade-offs

Case	Time	Space	Why
Merge sort (arrays)	`O(n log n)` best, average, worst	`O(n)`	Log₂ n levels, each merging every element once. Counted on n = 1024: 5120 comparisons for sorted input, 5120 for reversed, 8914 for a scrambled one. The bounds are ½·n·log₂ n = 5120 and n·log₂ n − n + 1 = 9217.
Merge sort (linked list)	`O(n log n)`	`O(log n)`	Merging relinks nodes instead of copying, so the buffer disappears; only the recursion stack is left.
Quicksort	`O(n log n)` average, `O(n²)` worst	`O(log n)` typical	In place and cache-friendly, but a bad pivot sequence degrades it and it is not stable.
Insertion sort	`O(n²)` worst, `O(n)` sorted	`O(1)`	Beats everything on tiny or nearly sorted input, which is why hybrids use it for small pieces.
Heap sort	`O(n log n)`	`O(1)`	Guaranteed and in place, but jumps around memory and is not stable.

Merge sort buys a guarantee and stability at the price of a second array. Input order barely moves the cost: the three runs above sit between 5120 and 9217 comparisons, a factor of two at most, whereas quicksort’s worst case is a different complexity class. The top-down code copies slices at each level; for n = 1024 the slices alone copy 10240 elements, which is n·log₂ n. Allocating one scratch array up front and merging back and forth between it and the input avoids that churn without changing the asymptotics.

Common mistakes

Using < instead of <= in the merge
On a tie, < takes the right element first, so equal keys swap. Sorting records [2x, 1a, 2y, 1b] by number gives 1a 1b 2x 2y with <= and 1b 1a 2y 2x with <. The numbers are sorted either way; only the stability is gone, which matters when you sort by one column after another.
Forgetting to drain the leftover run
When one run empties first, the other still holds its largest elements. A merge that stops at the end of the loop turns merge([1, 2], [3, 4]) into [1,2] and silently drops the whole right run. The fix is the final out + L[i:] + R[j:].
A base case that misses the empty list
Testing len(a) == 1 instead of <= 1 lets [] split into [] and [] forever, since 0 // 2 is 0. The recursion never shrinks and the stack overflows. Sorting an empty input is exactly the case a caller will eventually pass.
Treating it as in place
The Python version above returns a new list. Calling merge_sort(arr) and ignoring the result leaves arr in its original order. Either assign the result or write the merged output back into the input range.
Allocating inside the merge on every call
Building fresh slices at every level is correct but wasteful: n = 1024 copies 10240 elements in slices before any comparison happens, and each merge then allocates again. Use one scratch array of size n, allocated once.

Where this shows up

Data that does not fit in memory
Sort chunks that do fit, write each sorted chunk out, then merge the chunks in a single streaming pass. The merge needs only the front element of each chunk, which is why the same idea scales from two runs to hundreds.
Sorting by several keys
A stable sort lets you sort by the secondary key first and the primary key second and get the right combined order. That is a property of the <= tie rule, not an extra feature.
Counting inversions
Extend the merge to add the number of waiting left-run elements each time a right-run element goes first, and the sort also counts out-of-order pairs. On the page’s input that gives 6, matching a brute-force check over all 15 pairs. Rank-correlation measures and “how unsorted is this?” questions use it.
Linked lists and parallel work
A linked list has no random access, but merging only ever reads the front of each list, so merge sort needs no copying there. The two halves are also independent, so they can be sorted on separate threads and merged afterwards.

RUN IT YOURSELF

Merge sort, in Python & TypeScript

The same merge sort in both languages, running for real in your browser — Python via WebAssembly, TypeScript transpiled on the fly. Switch tabs to compare them, read the numbered comments, edit anything, and hit Run (or ⌘/Ctrl + Enter).

HOW TO READ THE CODE — 4 IDEAS

A list of 0 or 1 items is already sorted — the base case (step 1).
Split down the middle and sort each half (step 2).
Merge two sorted halves by repeatedly taking the smaller front item (step 3).
Append whatever is left on one side, and the whole list is sorted (step 4).

CPython · WebAssembly

QUICK CHECK

Did it stick?

See every answer, with the reasoning

What is the worst-case time complexity of merge sort?
Answer: O(n log n) — There are ~log n merge levels, each doing O(n) work — and no input changes that, so worst case equals average: O(n log n).
Why is merge sort stable?
Answer: On a tie it takes the left run's element first — When L[i] == R[j] the merge picks L[i] first (<=), so equal elements keep their original order.
What is merge sort's main trade-off versus quicksort?
Answer: It needs O(n) extra memory — The linear merge needs a temporary buffer the size of the data — O(n) extra memory is the price of the guaranteed time.

FAQ

Merge sort, answered

What is merge sort?

Merge sort is a divide-and-conquer sort: split the array in half until each piece is one element, then merge neighbouring sorted pieces back together. Because merging is linear and there are ~log n levels, it always runs in O(n log n).

What is the time complexity of merge sort?

O(n log n) in the best, average and worst case — there is no bad input. The cost is O(n) extra memory for the merge buffer.

Is merge sort stable?

Yes. When two elements are equal the merge keeps the left-run one first (<=), preserving original order — which is why it's chosen when stability matters.

Merge sort vs quicksort?

Merge sort guarantees O(n log n) and is stable but needs O(n) memory. Quicksort is in-place and usually faster but has an O(n²) worst case and isn't stable. Quicksort for in-memory arrays; merge sort for linked lists, external sorting, or when a guarantee matters.

Why does merge sort need extra memory?

Merging two runs needs somewhere to write the combined result while still reading both inputs — an O(n) temporary buffer. In-place merges exist but are complex and slow.

Where is merge sort used in real life?

External sorting of disk-sized data, sorting linked lists, and stable library sorts (Timsort, Java's object sort) are merge-sort hybrids.

▶ Watch it explained

Merge Sort: Time and Space Complexity, From First Principles

Finished this one? 0 / 99 Algorithms done

NextQuicksort: The Pivot Pit Next on the “The comparison sorts” ladder · rung 2 of 4

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

More Algorithms

Explore more

Algorithms →