Divide & Conquer
Think of it like this
You have 1000 sorted cards and need to put them all in sorted order with a partner. Instead of sorting them all yourself, you each take 500, sort your half, then you merge the two sorted halves together.
Your partner does the same thing recursively (splitting their 500 into two 250s). Eventually the problem is so small (1 card) that it's trivially solved. This is merge sort, and it's the template for all divide-and-conquer algorithms.
Split until trivial: Combine on the way back up:
[8,3,5,1,2,7,4,6] [1,2,3,4,5,6,7,8]
↙ ↘ ↗ ↖
[8,3,5,1] [2,7,4,6] [1,3,5,8] [2,4,6,7]
↙ ↘ ↙ ↘ ↗ ↖ ↗ ↖
[8,3][5,1] [2,7][4,6] [3,8][1,5] [2,7][4,6]
↙↘ ↙↘ ↙↘ ↙↘
[8][3][5][1][2][7][4][6] ← base cases (single elements)The Three Steps
- Divide: Split the problem into smaller subproblems (usually halves)
- Conquer: Solve each subproblem recursively (base case = trivially small)
- Combine: Merge the solutions to get the full answer
The power: if combining is O(n) and you split in half each time, the total cost is O(n log n), instead of O(n²) for the naive approach.
Merge Sort, The Classic
function mergeSort(arr) {
// Base case: a single element is already sorted
if (arr.length <= 1) return arr;
// Divide
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid)); // conquer left
const right = mergeSort(arr.slice(mid)); // conquer right
// Combine
return merge(left, right);
}
function merge(left, right) {
const
Time: O(n log n) in all cases. Space: O(n) for the merge buffer.
Quick Sort, Divide Around a Pivot
Instead of splitting at the midpoint, pick a pivot and partition: all elements smaller go left, larger go right. Then recurse on each partition.
arr = [3, 6, 8, 10, 1, 2, 1] pivot = arr[last] = 1
Partition:
Elements ≤ 1: [1, 1] (left partition)
Pivot: [1] (in final position)
Elements > 1: [3, 6, 8, 10, 2] (right partition)
Recurse on [1,1] and [3,6,8,10,2]...function quickSort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
const pivotIdx = partition(arr, low, high);
quickSort(arr, low, pivotIdx - 1);
quickSort(arr, pivotIdx + 1, high);
}
}
function partition(arr, low, high) {
const pivot = arr[high];
let i = low - 1; // tracks the boundary of the "≤ pivot" partition