Merge Sort & Divide-and-Conquer
Split the problem until it is trivial, then rebuild the answer — how merge sort achieves O(n log n) in every case and why that makes it the foundation of serious sorting.
What you'll learn
- Divide and conquer means split until trivial, solve each piece, then combine — merge sort is the textbook example
- Merge sort is O(n log n) in all cases (best, average, worst) because the recurrence T(n)=2T(n/2)+O(n) always solves to n log n
- The algorithm is stable (equal elements keep their original order) and needs O(n) extra space for the merge buffer
- Stability + predictable cost make merge sort the basis of Python's Timsort and most external/big-data sort routines
Before you start
Picture a deck of cards scattered face-up on a table. How would you sort them by hand if you could only compare two cards at a time?
One approach: split the deck in half, sort each half separately, then merge the two sorted halves into one. But sorting each half is the same problem at half the size — so split again. And again. Eventually every pile is one card. A single card is trivially sorted. Then you work backwards: merge two one-card piles into a sorted two-card pile, merge two two-card piles into a sorted four-card pile, and so on until the whole deck is sorted.
That is merge sort. The idea of breaking a problem into smaller copies of itself, solving each, and combining the results is called divide and conquer — one of the most important patterns in all of computer science.
The three-step pattern
Every divide-and-conquer algorithm follows the same skeleton:
- Divide — split the input into two (or more) sub-problems of roughly equal size.
- Conquer — solve each sub-problem recursively. When the sub-problem is small enough to solve directly (the base case), do so without recursing.
- Combine — merge the sub-solutions into an answer to the original problem.
For merge sort specifically:
- Divide: split the array at its midpoint.
- Conquer: sort the left half and the right half independently (recursively).
- Base case: an array of 0 or 1 elements is already sorted — return it as-is.
- Combine: merge two sorted halves into one sorted array by walking both with a pointer and always taking the smaller front element.
The widget above shows all three stages. Watch how splitting goes down the tree until every leaf is a single element (depth = log₂8 = 3), then merging goes back up, producing larger and larger sorted runs until the root holds the complete sorted array.
The merge step in detail
The merge is where the real work happens. Given two sorted arrays left and right, you maintain one pointer into each and repeatedly take the smaller element:
left = [3, 27, 38]
right = [1, 9, 43]
compare 3 and 1 → take 1 → result [1]
compare 3 and 9 → take 3 → result [1, 3]
compare 27 and 9 → take 9 → result [1, 3, 9]
compare 27 and 43 → take 27 → result [1, 3, 9, 27]
compare 38 and 43 → take 38 → result [1, 3, 9, 27, 38]
right exhausted → copy 43 → result [1, 3, 9, 27, 38, 43]Each merge of two halves of total size k does at most k comparisons. That is the O(n) combine step that drives the recurrence.
Runnable implementation
Complexity
| Property | Value |
|---|---|
| Best case | O(n log n) |
| Average case | O(n log n) |
| Worst case | O(n log n) |
| Space | O(n) auxiliary |
| Stable | Yes |
| In-place | No |
The O(n) extra space is the price of stability and guaranteed performance. In-place means an algorithm sorts using only a constant amount of memory beyond the input array itself. Merge sort is not in-place: the merge step needs a temporary buffer to hold the merged output — you cannot merge two sorted subarrays in-place without losing the ordering information.
Why stability matters
A sort is stable if elements that compare as equal appear in the output in the same relative order as in the input. This matters whenever you sort by one key and want to preserve a previous sort by another key.
Example: a table of students sorted first by grade, then by name. A stable sort on name will keep students with the same name in grade order. An unstable sort might scramble them.
Merge sort is stable because the merge step uses <= — when two elements are equal it always takes the left (earlier) one first.
Where merge sort lives in the real world
Python’s Timsort is a hybrid of merge sort and insertion sort. It detects already-sorted “runs” in the input, then merges them using a merge sort strategy. Python’s list.sort() and sorted() are Timsort — stable and O(n log n) worst-case.
External sort (sorting data too large to fit in RAM) is essentially merge sort. You sort chunks that fit in memory, write each sorted chunk to disk, then do a k-way merge of the chunks. The divide-and-conquer structure maps perfectly onto I/O-bounded storage.
Parallel sort algorithms (used in MapReduce, Spark, and similar systems) partition data across machines, sort each partition independently, then merge across the network — the same split/merge skeleton, applied at datacenter scale.
Quick check
Quick check
Practice this in an interview
All questionsSort intervals by start time. Then walk through them once: if the current interval's start is at or before the end of the last merged interval, merge by extending the end. Otherwise, the current interval is disjoint — push it onto the result. Sorting costs O(n log n); the merge pass is O(n).
Use a dummy head node to avoid special-casing the result's first element. Walk both lists with two pointers, always appending the smaller current node to the result. When one list is exhausted, append the remainder of the other. O(n + m) time, O(1) space.
Even after rotation, one of the two halves around mid is always fully sorted. Check which half is sorted, then decide whether the target falls inside it. If yes, narrow to that half; if no, search the other. This keeps binary search's O(log n) guarantee.
Binary search halves the search space each iteration to find a target in O(log n). The tricky part is not the idea but the boundary conditions: closed vs. half-open intervals, how to update lo/hi, and when to use lo < hi vs. lo <= hi. One clean template eliminates all the classic bugs.