Merge Sort: Divide & Conquer

Merge sort is the cleanest example of divide and conquer, and it guarantees O(n log n) on every input. It is also how databases sort data too big for memory.

intermediate⏱ 12 min read

←Builds on

0Recursion & the Call StackMerge sort calls itself on each half and merges on the way back up.2Elementary SortsSplitting the work in half is what beats the O(n²) of the elementary sorts.

Leads to→

2Quicksort & PartitioningQuicksort is divide and conquer too, but it does its work before the recursive calls, not after.2Counting SortComparison sorts cannot beat n log n; counting sort escapes by never comparing.2Comparators & Stabilitystd::stable_sort is merge sort, which is why equal elements keep their order.+Suffix ArraySuffixes are sorted by doubling prefix lengths, an O(n log n) sorting job at heart.

1Learn 2Play 3Check 4Practice

Learn

The idea, the mechanics and the cost.

01Divide and conquer

Merge sort follows a recipe in three steps:

Divide: split the array into two halves at mid = (lo + hi) / 2.
Conquer: sort each half recursively. A piece of one element is already sorted: that is the base case.
Combine: merge the two sorted halves into one sorted array.

All the real work happens in the combine step. The splitting just keeps cutting until pieces have size 1, then the merges rebuild the array from the bottom up, each time joining two sorted runs into a longer one.

02The merge: two pointers

Merging two sorted lists is a two-pointer walk. Pointer i starts at the front of the left half, j at the front of the right half.

Compare a[i] and a[j]; copy the smaller one into a buffer and advance that pointer.
When one side runs out, copy the rest of the other side.
Copy the buffer back into a[lo..hi].

Each step outputs one element, so merging m elements costs O(m). The buffer is why merge sort needs O(n) extra memory.

Use <= when comparing: on a tie take the left element first. That keeps equal keys in their original order, making merge sort stable.

03Why n log n

Draw the recursion as levels. Level 0 has one piece of size n, level 1 has two of size n/2, level 2 has four of size n/4, and so on.

On every level the merges together touch all n elements once: O(n) work per level. Halving n repeatedly reaches 1 after log₂ n levels. Total: O(n log n).

As a recurrence: T(n) = 2·T(n/2) + O(n) = O(n log n). Unlike quicksort this does not depend on the input at all: sorted, reversed or random, merge sort always does the same amount of work. For n = 10⁶ that is about 2·10⁷ steps instead of 10¹² for an O(n²) sort.

04Where merge sort shines

Pick merge sort (or a library stable sort, which is usually based on merge sort) when:

you need stability: std::stable_sort, Java's object sort and Python's Timsort are merge sorts
you sort a linked list: merging needs no random access and no extra array
the data does not fit in memory: external sorting merges sorted chunks from disk
you need a guaranteed worst case

The merge step is also a tool on its own. While merging, every time you take from the right half, all remaining left elements are larger: add their count and you have counted inversions in O(n log n).

The cost: O(n) extra memory, and somewhat slower than quicksort in practice for plain arrays of numbers.

Cost at a glance

Time (every case)O(n log n)

Merge two runs of total mO(m)

Extra memoryO(n)

Recursion depthO(log n)

Remember

Merge sort splits in half, sorts each half recursively and merges them with two pointers.
There are log n levels and each does O(n) merging, so it is O(n log n) on every input.
It is stable and works on linked lists, at the price of O(n) extra memory for arrays.

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the active range shrink as it splits, then the buffer fill with the smaller front each time during a merge.

Interactive visualizerfocus here, then space ← →

Merge sort · active range [0, 7]

Auxiliary buffer

∅

Merge sort by divide & conquer: split the 8-element array until pieces are size 1, then merge sorted pieces back together.

Pseudocode

 1 mergeSort(lo, hi): 2   if lo >= hi: return       // one element is sorted 3   mid = (lo+hi)/2 4   mergeSort(lo,mid); mergeSort(mid+1,hi) 5   merge: pick the smaller front of the two halves 6   … until one half empties 7   copy the merged buffer back

1 / 1

Check

Three questions. Pick an answer to see why.

Merging [2, 7, 9] and [3, 4, 10]: what are the first four elements written to the buffer?

How does merge sort's running time on an already sorted array compare with a random one?

Why compare with <= (take from the left on ties) during the merge?

Practice

Real problems to lock it in, easiest first.

LeetCodeMerge Sorted Array beginner↗LeetCodeMerge Two Sorted Lists beginner↗LeetCodeSort an Array intermediate↗LeetCodeSort List intermediate↗LeetCodeCount of Smaller Numbers After Self advanced↗