Divide and Conquer Algorithms
Merge sort and quick sort using the divide-and-conquer approach, followed by probabilistic and randomized analysis, the Hiring Problem, matrix multiplication, Strassen's method, and powering a number.
6.1Merge Sort — Overview
Merge sort is the textbook Divide and Conquer algorithm:
- Divide — split the array into two halves.
- Conquer — recursively sort each half.
- Combine — merge the two sorted halves into one sorted array.
6.2The Merge Operation
Merging is the heart of merge sort: given two already-sorted lists, produce one sorted list from them. Keep a pointer into each input (i into A, j into B) and a write pointer into the output. Compare the two pointed-at elements, copy the smaller one out, and advance that pointer (and the output pointer):
if A[i] <= B[j]: C[m] = A[i]; i++; m++ else: C[m] = B[j]; j++; m++
When one list runs out, the other is already sorted — just copy the rest of it across directly.
Merging two lists of total length n takes O(n) time — every element is looked at, and copied, exactly once.
6.3Merge Algorithm & Its Space Cost
def merge(left_half, right_half, arr):
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] <= right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
# Copy any remaining elements from the left half
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
# Copy any remaining elements from the right half
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
show answer
In the full merge-sort implementation,
slicing creates left_half and
right_half; together they hold n elements. The merge
writes those values back into arr. Therefore this
implementation needs auxiliary space proportional to the input size.
6.4Merging Without Extra Space
Can we merge two sorted arrays A (size n) and B (size m) using only O(1) extra space? One approach: compare from the tail of A against the head of B, swapping whenever they are out of order, then re-sort each array afterward.
def merge_two_arrays_no_extra_space(A, B):
n, m = len(A), len(B)
left, right = n - 1, 0
while left >= 0 and right < m:
if A[left] > B[right]:
swap(A[left], B[right])
left -= 1
right += 1
else:
break
sort(A)
sort(B)
The idea: any element of A that is larger than an element of B must belong on B's side (and vice versa) once both are merged, so swapping the offending pairs from the two ends inward gets every value roughly into its correct array — re-sorting each array afterward finishes the job.
6.5Gap-Merge — a Shell-Sort-Style In-Place Merge
A cleverer O(1)-extra-space technique borrows the idea behind Shell sort: instead of only comparing neighbours, compare elements a fixed gap apart across the two arrays laid end to end, swap any out-of-order pair, then shrink the gap and repeat until the gap reaches 1.
def next_gap(gap):
if gap <= 1:
return 0
return (gap // 2) + (gap % 2)
def merge_gap(arr1, arr2):
n, m = len(arr1), len(arr2)
total = n + m
gap = next_gap(total)
while gap > 0:
left = 0
right = left + gap
while right < total:
if left < n and right >= n:
if arr1[left] > arr2[right - n]:
arr1[left], arr2[right - n] = arr2[right - n], arr1[left]
elif left >= n:
if arr2[left - n] > arr2[right - n]:
arr2[left - n], arr2[right - n] = arr2[right - n], arr2[left - n]
else:
if arr1[left] > arr1[right]:
arr1[left], arr1[right] = arr1[right], arr1[left]
left += 1
right += 1
gap = next_gap(gap)
For n = 4, m = 5, and total = 9, the gap sequence runs 5 → 3 → 2 → 1 (each step: ceil(gap/2)), with one comparison-and-possible-swap pass at each gap width, finishing fully sorted after the gap-1 pass.
Let N = n + m. There are O(log N) gap values, and each pass performs at most N comparisons. Hence both the average- and worst-case running times are O(N log N) for this implementation, with O(1) auxiliary space.
6.6Merge Sort — the Full Algorithm
def merge_sort(arr):
if len(arr) <= 1:
return
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
# Recursively sort each half
merge_sort(left_half)
merge_sort(right_half)
# Merge left_half and right_half back into arr
merge(left_half, right_half, arr)
merge(...) call, or a completed return.merge_sort frame keeps its parameter reference, mid, references to left_half and right_half, and the instruction at which execution must resume. A merge(...) frame keeps references to the two sorted halves, the destination list and its return point. The demonstration treats the internal merge operation as one step.merge_sort divides its range and pushes the left recursive call above the suspended caller.merge(...) frame. Its complete merge is shown as one operation.merge_sort frame returns its sorted range to its own caller.6.7Merge Sort — Time Analysis
Every level of the recursion touches every element exactly once (across all the merges at that level combined), and there are log₂n levels:
6.8Merge Sort — Space, Overall Verdict
Each merge needs temporary arrays sized to the pieces being merged, but those temporaries are freed as soon as that merge call returns — at any single moment the temporaries in use add up to Θ(n), plus Θ(log n) for the recursion's own call stack.
| Best | Worst | Average | |
|---|---|---|---|
| Time | Θ(n log n) | Θ(n log n) | Θ(n log n) |
Recurrence: T(n) = 2T(n/2) + Θ(n). Space: Θ(n) additional (for the temporary merge arrays).
Advantages
- Guaranteed Θ(n log n) time — no input can make it worse.
- Stable sort (preserves the relative order of equal elements) — insertion sort and bubble sort are stable too.
- Supports external sorting — only part of the data needs to be in RAM at once, useful for datasets too big to fit in memory.
Disadvantages
- Needs extra space proportional to n — not an in-place algorithm.
- Recursion overhead makes it a poor choice for small n — insertion sort is typically faster for n < 32 in practice.
show answer
The recursion always splits the array in half, so the deepest chain of nested calls has length log₂n — that is the maximum number of stack frames alive at once.
6.9Quick Sort — Strategy
Quicksort takes the opposite approach to merge sort. Pick an element as the pivot, and rearrange the array so that the pivot lands in its final, correct sorted position — with every smaller element to its left and every larger element to its right (each side may be internally unordered). Then recurse on the left and right parts.
6.10Quick Sort — Partitioning and Full Execution
The classic partition scheme: take the pivot as the first element, and scan with two pointers — i moving right looking for something ≥ pivot, j moving left looking for something ≤ pivot. Whenever they find such a pair with i still left of j, swap them. When the pointers cross, swap the pivot into its resting place at j.
partition(A, low, high):
pivot = A[low]
i, j = low + 1, high
while True:
while i <= high and A[i] <= pivot: i += 1
while A[j] > pivot: j -= 1
if i >= j: break
swap(A[i], A[j])
swap(A[low], A[j])
return j
QuickSort frame keeps the array reference, low and high, the pivot index returned by partition, and the instruction at which execution must resume. During partitioning, the active call also uses the pivot value and pointer positions i and j. The demonstration shows partitioning within the active QuickSort call.QuickSort(A, low, high) is pushed above its suspended caller, becoming the active top frame.i and j, and fixes the pivot in its final position.The first partition produces [2,1,3,4,7,6,5,8], placing pivot 4 at index 3. Quick Sort must then continue recursively on both sides; the complete execution finishes with [1,2,3,4,5,6,7,8].
6.11QuickSort() Algorithm
QuickSort(A, low, high):
if low < high:
k = partition(A, low, high)
QuickSort(A, low, k - 1)
QuickSort(A, k + 1, high)
k. Its position is final, so neither recursive call should include it again.6.12Quick Sort — Best and Worst Case
6.13Quick Sort — Discussion Questions
show answer
An already sorted (or reverse-sorted) array, when the pivot is chosen as the first or last element every time — each partition then produces the most unbalanced split possible (empty on one side).
show answer
Choose a pivot uniformly at random (or randomly shuffle the input once before sorting). This prevents a fixed input order from repeatedly forcing extreme pivots and gives expected Θ(n log n) time. It improves the expected behaviour; the theoretical worst case remains Θ(n²).
show answer
6.14Case Study: Hybrid Quicksort
A manager tracks cumulative tasks completed per employee (this week's count is added to last week's running total) and finds the MVP by running QuickSort — first element as pivot — on the totals, then reading off the largest.
- What is the time complexity in a typical week?
- After a two-week holiday where nobody works, the office reopens and the manager must announce the MVP again. What changes?
- How should the manager adapt QuickSort for this situation?
show guided answer
- For a random ordering of totals, first-pivot quicksort has expected time Θ(n log n).
- If the previously sorted cumulative array is retained and no totals change during the holiday, the next input is already sorted. Choosing the first element as pivot gives Θ(n²).
- Randomly shuffle the records or choose each pivot randomly; the expected running time becomes Θ(n log n).
Modify quicksort's base case: once a subarray shrinks to fewer than k elements, sort it directly with insertion sort instead of recursing further.
Argue that the randomized version runs in O(nk + n log(n/k)) expected time.
6.15Probabilistic Analysis vs Randomized Analysis
Two different ways randomness enters an algorithm's analysis — easy to conflate, worth telling apart precisely:
| Probabilistic analysis | Randomized analysis | |
|---|---|---|
| Source of randomness | the input distribution | the algorithm's own choices |
| Algorithm itself | deterministic | makes random choices, even on a fixed input |
| Quicksort example | pivot = first element always; assume input permutations are equally likely → average O(n log n), but worst case (sorted input) is still O(n²) | pivot chosen uniformly at random each call → expected O(n log n) for any fixed input |
6.16The Hiring Problem
You need to hire an office assistant:
- An agency sends one candidate per day, numbered 1 to n, interviewed in that order.
- Interviewing costs a small fee cᵢ; hiring costs a large fee cℎ (it involves firing the current assistant and onboarding the new one).
- Strategy: after each interview, hire that candidate only if they are better than the current assistant — so the best-so-far is always on staff.
- A dummy "candidate 0", worse than everyone, is the initial placeholder assistant.
Total cost for m actual hires: O(cᵢn + cℎm). The cᵢn term is fixed — all n candidates get interviewed regardless. The interesting question is m, the number of hires, which depends entirely on the order candidates arrive in.
If candidates arrive in strictly increasing quality order, every single one is hired: m = n, so the hiring cost is O(cℎn) — the worst possible outcome. In reality we don't control (or know) the arrival order, which is exactly what motivates an average-case analysis instead.
6.17Indicator Random Variables
A simple but powerful tool for turning probability questions into expectation questions (and vice versa).
E[XA] = Pr{A}
Proof. E[X_A] = E[I{A}]
= 1 · Pr{A} + 0 · Pr{not A}
= Pr{A}. ∎
Let Xi = 1 if flip i is heads, else 0. A fair coin gives E[Xi] = Pr{heads} = 1/2 for every flip. Let X = X₁ + X₂ + ⋯ + Xₙ be the total number of heads. By linearity of expectation (which needs no assumption that the flips are independent!):
E[X] = E[X₁] + E[X₂] + ⋯ + E[Xₙ] = n · (1/2) = n/2
A satisfying confirmation of the obvious answer — and the exact technique we now aim at the much less obvious Hiring Problem.
6.18Solving the Hiring Problem with Indicator Variables
Assume candidates arrive in uniformly random order. Define Xi = 1 if candidate i is hired (i.e. candidate i is better than all of candidates 1..i−1), else 0. We want E[X], the expected number of hires.
Candidate i is hired exactly when they are the best among the first i candidates seen so far. In a random arrival order, each of the first i candidates is equally likely to be the best of that group — so Pr{candidate i is hired} = 1/i, and by the Lemma above, E[Xi] = 1/i.
Total hires X = X₁ + X₂ + ⋯ + Xn. By linearity of expectation:
E[X] = E[X₁] + E[X₂] + ⋯ + E[Xₙ]
= 1/1 + 1/2 + 1/3 + ⋯ + 1/n
= Hₙ (the n-th harmonic number)
= ln n + O(1)
HIRE-ASSISTANT(n) 1 best = 0 // candidate 0 is a least-qualified dummy 2 for i = 1 to n 3 interview candidate i 4 if candidate i is better than candidate best 5 best = i 6 hire candidate i RANDOMIZED-HIRE-ASSISTANT(n) 1 randomly permute the list of candidates 2 HIRE-ASSISTANT(n)
6.19Randomized Quicksort via Indicator Variables
The same technique analyses randomized quicksort. Let Xk = 1 if the partition step produces a k : (n−k−1) split (k = 0, …, n−1), else 0. With a uniformly random pivot and distinct elements, every split is equally likely:
E[X_k] = Pr{X_k = 1} = 1/n for each k = 0, …, n−1
T(n) = Σ X_k · (T(k) + T(n−k−1) + Θ(n))
k=0..n−1
Taking expectations and using linearity:
E[T(n)] = (1/n) · Σ (E[T(k)] + E[T(n−k−1)]) + Θ(n)
k=0..n−1
6.20Matrix Multiplication
For n×n matrices A and B, the product C = A·B is defined entrywise by C[i][j] = Σk A[i][k]·B[k][j]. The naive triple-nested loop computes all n² entries, each needing n multiply-adds:
Divide and Conquer
Split each n×n matrix into four (n/2)×(n/2) blocks. Block multiplication follows ordinary matrix rules, just with blocks standing in for numbers:
C11 = A11·B11 + A12·B21 C12 = A11·B12 + A12·B22 C21 = A21·B11 + A22·B21 C22 = A21·B12 + A22·B22
def matrix_multiply(A, B, n):
if n <= threshold:
return naive_multiply(A, B)
C11 = matrix_multiply(A11, B11, n/2) + matrix_multiply(A12, B21, n/2)
C12 = matrix_multiply(A11, B12, n/2) + matrix_multiply(A12, B22, n/2)
C21 = matrix_multiply(A21, B11, n/2) + matrix_multiply(A22, B21, n/2)
C22 = matrix_multiply(A21, B12, n/2) + matrix_multiply(A22, B22, n/2)
return combine(C11, C12, C21, C22)
This makes 8 recursive multiplications of (n/2)-sized blocks, plus Θ(n²) work to add the block products together:
6.21Strassen's Algorithm
Strassen's insight: with seven cleverly chosen products (instead of eight), the same four output blocks can be recovered using only extra additions — additions are cheap (Θ(n²)), multiplications are what we want to save.
C11 = M1 + M4 − M5 + M7 C12 = M3 + M5 C21 = M2 + M4 C22 = M1 − M2 + M3 + M6
6.22Powering a Number
Problem: compute an for a natural number n.
Divide and conquer (exponentiation by squaring):
⎧ (a^(n/2))² if n is even
a^n = ⎨
⎩ a · (a^((n−1)/2))² if n is odd
def power(a, n):
if n == 0:
return 1
half = power(a, n // 2)
if n % 2 == 0:
return half * half
return a * half * half