Classic divide-and-conquer algorithms
Merge sort, counting inversions, the median of two sorted arrays, and majority voting. · 11 min read
Merge sort & counting inversions
Merge sort splits, sorts each half, and merges in O(n) — T(n) = 2T(n/2) + O(n) = O(n log n). The same merge step counts inversions (out-of-order pairs): when an element from the right half is taken before elements remaining on the left, each of those left elements forms an inversion.
Interactive visualization: n work per level × log n levels — step through it frame by frame on this page.
Median of two sorted arrays
Binary-searching the partition point of the two arrays finds the combined median in O(log(m+n)) — a subtle but classic divide-and-conquer on the answer space (an O(m+n) merge also works and is a fine first solution).
Majority element
The majority of an array is the majority of one of its halves, so D&C finds it by combining the two halves' candidates — O(n log n). Boyer–Moore voting does the same job in a single O(n) pass with O(1) memory by cancelling non-matching pairs.
Other classics
- Closest pair of points —
O(n log n)by splitting the plane and checking a thin strip across the divide. - Karatsuba multiplication — multiply big numbers in
O(n^1.585)by reducing four sub-multiplications to three. - Quickselect — partition like quicksort but recurse into only one side for the k-th element in
O(n)average.
Practice: Count Inversions (Hard) — How far is the array from sorted? Count out-of-order pairs in O(n log n).
Practice: Majority Element (Medium) — The element appearing more than n/2 times.
Practice: Median of Two Sorted Arrays (Hard) — Find the median of two sorted arrays as a single value.