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.

ALGORITHMS · 04 / MERGE SORT

The Cascade.

Q: What is the time complexity of merge sort?

Merge sort runs in O(n log n) time in the best, average and worst case — there is no bad input. Each of the ~log2(n) merge levels does O(n) work to combine the runs. The trade-off is space: it needs O(n) extra memory for the temporary buffer used while merging.

Q: Is merge sort stable?

Yes. Merge sort is stable: when two elements compare equal, the merge step keeps the one from the left run first, preserving their original order. This is why merge sort is preferred when stability matters, such as sorting records by a secondary key.

Q: Why does merge sort need extra memory?

Merging two sorted runs into one requires somewhere to write the combined result while you still need to read from both inputs, so a standard merge uses an O(n) temporary buffer. In-place merge variants exist but are complex and slower, so most implementations accept the extra memory.

Q: Where is merge sort used in real life?

External sorting of data too big for memory (merging sorted chunks from disk), sorting linked lists where it needs no random access, stable library sorts (Python's Timsort and Java's sort for objects are merge-sort hybrids), and anywhere a guaranteed worst-case time matters.

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.

QUICK CHECK

Did it stick?

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.

Finished this one? 0 / 5 Algorithms done

More Algorithms

Explore more from Vibe Engines

Handbooks →

Roadmaps →

Prompt Engineering Roadmap

System Designs →

AI System Designs →

Labs →

Gradient Descent: The Descent