1Understand
The idea
Split the input into halves, solve each half recursively, and combine the two answers. The combine step is the heart of it: in merge sort, merging two sorted halves is linear, which gives O(n log n). Many counting problems (inversions, pairs across the halves) become cheap because both halves are already sorted when you combine.
Intuition
Divide and conquer splits the input, solves each piece recursively, then combines the answers. The combine step is the heart: merge sort's linear merge of two sorted halves is what yields O(n log n).
Many counting problems become easy at combine time because both halves are already sorted, inversions, cross-half pairs, closest points. The recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n).
Quickselect is the same family with a different combine: partition around a pivot and recurse into only one side for expected O(n).
What you will be able to do
- Write the split, recurse and combine steps
- Derive O(n log n) from the recurrence
- Partition around a pivot
When to use it
- Implement a sort without sort()
- K-th largest in expected O(n)
- Count pairs across two halves (inversions)
- Build something from both halves
2See it
Walkthrough
Merge sort split and merge
a = [4, 1, 3, 2], split to singles, merge sorted halves.
1 / 4
Split at mid. Left [4, 1], right [3, 2].
Live template
Line 3 active
Complexity: time O(n log n); quickselect O(n) expected, space O(n)
Typical cost O(n log n) time and O(n) merge space (or O(log n) stack if you avoid slicing). Quickselect is expected O(n), worst O(n²) with bad pivots. Prefer index bounds over slicing at every level to avoid hidden O(n) copies.
Read the walkthrough as text
Count inversions while merging. Array [2, 4, 1, 3].
- Sort left
[2, 4]and right[1, 3]recursively (0 inversions inside each). - Merge:
1comes from the right while2and4remain on the left → those two form inversions with1. - Next take
2, then3(no new cross inversions with leftover4), then4. - Total cross inversions: 2. Whole-array inversions = left + right + cross.
The merge walk is O(n); the full sort-shaped recursion is O(n log n).
3Recognise it
Kinds of problems (7)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Merge sort
Example. Sort an array without calling sort().
How. Split mid, sort halves recursively, merge two sorted lists in O(n).
Quicksort and partitioning
Example. In-place sort around a pivot.
How. Partition so left ≤ pivot ≤ right, then recurse on both sides.
Quickselect (k-th element)
Example. K-th smallest in expected O(n).
How. Partition once; recurse only the side that contains index k, average linear time.
Counting inversions during merge
Example. Count pairs i < j with a[i] > a[j].
How. When merging, left item > right item adds (mid - i + 1) inversions.
Combining answers across the midpoint
Example. Best subarray sum crossing the center (max subarray).
How. Recursively solve halves; combine with one linear scan from mid outward.
Recursive subdivision of a grid (quad tree)
Example. Build a quadtree on a 2-D grid or summarize regions.
How. Split grid into four quadrants; base case when region is uniform or size 1.
Split around elements that cannot be in the answer
Example. Discard candidates that fail a global bound in optimization search.
How. Partition “feasible / infeasible” and only recurse on the promising side.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Base case too late
Why it happens. You want to keep splitting until the array is empty, not “too early”.
How it fails. merge_sort with `if not a: return a` only, recursion never stops on single-element slices and overflows.
Fix. Base case len(a) <= 1: return a (or lo == hi for index-based splits).
Merge leftovers dropped
Why it happens. As soon as one half is exhausted, you want to stop merging.
How it fails. Merge stops when i == n1 but j < n2, remaining right elements never appear in the output.
Fix. After the main loop, copy all leftover elements from whichever half still has indices.
Bad pivot
Why it happens. The first element is always handy as a pivot.
How it fails. Already-sorted array with pivot = a[lo]: partitions are size 0 and n−1 every level → O(n²).
Fix. Random pivot, median-of-three, or quickselect’s “swap pivot to end” variation on structured input.
Slicing cost
Why it happens. a[:mid] and a[mid:] mirror the recurrence cleanly in code.
How it fails. Merge sort that slices at every level copies O(n log n) extra elements in Python.
Fix. Pass (lo, hi) indices, or one auxiliary buffer reused across levels.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.