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 result = [];
  let i = 0, j = 0;
  // Merge two sorted arrays into one sorted array — O(n)
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else                      result.push(right[j++]);
  }
  // Append remaining elements
  return result.concat(left.slice(i)).concat(right.slice(j));
}
 
// In-place merge sort (saves O(n) space — used in competitive programming)
function mergeSortInPlace(arr, l = 0, r = arr.length - 1) {
  if (l >= r) return;
  const mid = Math.floor((l + r) / 2);
  mergeSortInPlace(arr, l, mid);
  mergeSortInPlace(arr, mid + 1, r);
  mergeInPlace(arr, l, mid, r);
}

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
 
  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]]; // swap into left partition
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // place pivot
  return i + 1;
}

Time: O(n log n) average, O(n²) worst (already sorted + bad pivot). Space: O(log n) call stack.

The Master Theorem

Divide-and-conquer recurrences have the form: T(n) = a·T(n/b) + f(n)

a = number of subproblems
n/b = size of each subproblem
f(n) = cost of divide + combine step

Case	Condition	Result	Example
1	f(n) = O(n^(logb(a) - ε))	T(n) = O(n^logb(a))	Binary tree traversal: a=2, b=2, f=O(1) → O(n)
2	f(n) = O(n^logb(a) × log^k(n))	T(n) = O(n^logb(a) × log^(k+1)(n))	Merge sort: a=2, b=2, f=O(n) → O(n log n)
3	f(n) = Ω(n^(logb(a) + ε))	T(n) = O(f(n))	Dominated by combine step

Merge sort: a=2, b=2, f(n)=O(n) → Case 2 → O(n log n) ✓ Binary search: a=1, b=2, f(n)=O(1) → Case 1 → O(log n) ✓

Counting Inversions (Merge Sort Variant)

An inversion in an array is a pair (i, j) where i < j but arr[i] > arr[j]. Count them in O(n log n) by modifying merge sort — count inversions during the merge step.

function countInversions(arr) {
  if (arr.length <= 1) return { sorted: arr, count: 0 };
 
  const mid = Math.floor(arr.length / 2);
  const { sorted: left, count: leftCount } = countInversions(arr.slice(0, mid));
  const { sorted: right, count: rightCount } = countInversions(arr.slice(mid));
 
  const merged = [];
  let count = leftCount + rightCount;
  let i = 0, j = 0;
 
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      merged.push(left[i++]);
    } else {
      // left[i..] are all > right[j] (left is sorted), so count = left.length - i
      count += left.length - i;
      merged.push(right[j++]);
    }
  }
  return { sorted: merged.concat(left.slice(i), right.slice(j)), count };
}

Find the k-th Smallest Element (QuickSelect)

Don't sort the whole array — use partition to narrow down. Average O(n), worst O(n²).

function quickSelect(nums, k) {
  function select(low, high) {
    const pivotIdx = partition(nums, low, high);
    if (pivotIdx === k - 1) return nums[pivotIdx];
    if (pivotIdx < k - 1)   return select(pivotIdx + 1, high); // k is in right
    return select(low, pivotIdx - 1);                           // k is in left
  }
  return select(0, nums.length - 1);
}
// Example: find 3rd smallest in [3,2,1,5,6,4]
// partition → pivot finds its sorted position
// recurse only into the half containing position k-1

Closest Pair of Points (O(n log n))

A classic divide-and-conquer problem: find the two closest points out of n points in 2D.

Naive: check all pairs → O(n²)
 
Divide & conquer:
1. Sort points by x-coordinate
2. Split into left and right halves
3. Recursively find closest pair in each half (d = min(leftMin, rightMin))
4. Check if there's a closer pair that straddles the boundary
   (only points within distance d of the midline can do this)
5. Combine: min of left, right, and cross-boundary
 
Result: O(n log n)

Divide and Conquer (Merge Sort)

1 / 4

[38,27,43,3]

DIVIDE: Split the array in half.

Real-World Frontend Application

JavaScript's Array.prototype.sort(): The V8 engine uses Timsort (a merge sort variant) for arrays with more than ~10 elements
React component architecture: Literally divide-and-conquer on UI — break a complex page into independent, smaller components, then compose them. Each component only needs to know about its own subtree
Webpack/Vite code splitting: The bundler recursively splits the module graph into independent chunks (divide), bundles each (conquer), then links them at runtime (combine)
Canvas rendering pipelines: Many 2D renderers use spatial divide-and-conquer (quadtrees) — split the canvas into quadrants, only re-render quadrants that have changed

Merge Sort vs Quick Sort — When to Use Which

	Merge Sort	Quick Sort
Worst case	O(n log n) always	O(n²) if pivot is bad
Average case	O(n log n)	O(n log n)
Space	O(n) extra	O(log n) call stack only
Stability	✓ Stable	✗ Not stable
Cache performance	Moderate	Excellent (in-place)
Best for	Linked lists, stable sort required, guaranteed performance	Arrays, in-place needed

Common Mistakes

Mistake	What Goes Wrong	Fix
Missing base case	Infinite recursion → stack overflow	Always handle `n ≤ 1`
Off-by-one in midpoint	Skips elements or processes some twice	Use `Math.floor((l + r) / 2)` consistently
Incorrect merge in counting inversions	Misses or double-counts inversions	Count when right element is added (left[i] > right[j])
QuickSort worst case	O(n²) on sorted arrays	Use median-of-three pivot, or randomized pivot

Key Problems to Solve

#	Problem	Technique	Difficulty
1	Merge Sort	Classic D&C	Medium
2	Sort an Array	Merge/Quick sort implementation	Medium
3	Kth Largest Element	QuickSelect	Medium
4	Merge K Sorted Lists	Divide lists into pairs, merge	Hard
5	Count of Smaller Numbers After Self	Merge sort + inversions	Hard
6	Reverse Pairs	Modified merge sort	Hard
7	Majority Element	Divide then vote	Medium
8	Maximum Subarray	D&C approach (O(n log n), for practice)	Medium
9	Median of Two Sorted Arrays	Binary search (D&C on the search space)	Hard
10	Beautiful Array	Constructive D&C	Hard

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)

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]...

Case

Condition

Result

Example

f(n) = O(n^(logb(a) - ε))

T(n) = O(n^logb(a))

Binary tree traversal: a=2, b=2, f=O(1) → O(n)

f(n) = O(n^logb(a) × log^k(n))

T(n) = O(n^logb(a) × log^(k+1)(n))

Merge sort: a=2, b=2, f=O(n) → O(n log n)

f(n) = Ω(n^(logb(a) + ε))

T(n) = O(f(n))

Dominated by combine step

function quickSelect(nums, k) { function select(low, high) { const pivotIdx = partition(nums, low, high); if (pivotIdx === k - 1) return nums[pivotIdx]; if (pivotIdx < k - 1) return select(pivotIdx + 1, high); // k is in right return select(low, pivotIdx - 1); // k is in left } return select(0, nums.length - 1); } // Example: find 3rd smallest in [3,2,1,5,6,4] // partition → pivot finds its sorted position // recurse only into the half containing position k-1

Naive: check all pairs → O(n²) Divide & conquer: 1. Sort points by x-coordinate 2. Split into left and right halves 3. Recursively find closest pair in each half (d = min(leftMin, rightMin)) 4. Check if there's a closer pair that straddles the boundary (only points within distance d of the midline can do this) 5. Combine: min of left, right, and cross-boundary Result: O(n log n)

Merge Sort

Quick Sort

Worst case

O(n log n) always

O(n²) if pivot is bad

Average case

O(n log n)

Space

O(n) extra

O(log n) call stack only

Stability

✓ Stable

✗ Not stable

Cache performance

Moderate

Excellent (in-place)

Best for

Linked lists, stable sort required, guaranteed performance

Arrays, in-place needed

Mistake

What Goes Wrong

Fix

Missing base case

Infinite recursion → stack overflow

Always handle n ≤ 1

Off-by-one in midpoint

Skips elements or processes some twice

Use Math.floor((l + r) / 2) consistently

Incorrect merge in counting inversions

Misses or double-counts inversions

Count when right element is added (left[i] > right[j])

QuickSort worst case

O(n²) on sorted arrays

Use median-of-three pivot, or randomized pivot

Problem

Technique

Difficulty

Merge Sort

Classic D&C

Medium

Sort an Array

Merge/Quick sort implementation

Medium

Kth Largest Element

QuickSelect

Medium

Merge K Sorted Lists

Divide lists into pairs, merge

Hard

Count of Smaller Numbers After Self

Merge sort + inversions

Hard

Reverse Pairs

Modified merge sort

Hard

Majority Element

Divide then vote

Medium

Maximum Subarray

D&C approach (O(n log n), for practice)

Medium

Median of Two Sorted Arrays

Binary search (D&C on the search space)

Hard

Beautiful Array

Constructive D&C

Hard

Divide & Conquer

Divide & Conquer#

Think of it like this

The Three Steps

Merge Sort — The Classic

Quick Sort — Divide Around a Pivot

The Master Theorem

Counting Inversions (Merge Sort Variant)

Find the k-th Smallest Element (QuickSelect)

Closest Pair of Points (O(n log n))

Divide and Conquer (Merge Sort)

Real-World Frontend Application

Merge Sort vs Quick Sort — When to Use Which

Common Mistakes

Key Problems to Solve

Divide & Conquer

Divide & Conquer#

Think of it like this

The Three Steps

Merge Sort — The Classic

Quick Sort — Divide Around a Pivot

The Master Theorem

Counting Inversions (Merge Sort Variant)

Find the k-th Smallest Element (QuickSelect)

Closest Pair of Points (O(n log n))

Divide and Conquer (Merge Sort)

Real-World Frontend Application

Merge Sort vs Quick Sort — When to Use Which

Common Mistakes

Key Problems to Solve

Divide & Conquer

Divide & Conquer