33  Algorithm Design — Divide and Conquer

34 Algorithm Design — Divide and Conquer

Week 6, Session 1. CSS 343.

34.1 Warmup

Sort an Array (#912). Implement merge sort.

class Solution {
 public:
  vector<int> sortArray(vector<int>& nums) {
    mergeSort(nums, 0, nums.size() - 1);
    return nums;
  }
 private:
  void mergeSort(vector<int>& v, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(v, lo, mid);
    mergeSort(v, mid + 1, hi);
    merge(v, lo, mid, hi);
  }
  void merge(vector<int>& v, int lo, int mid, int hi) {
    vector<int> tmp;
    tmp.reserve(hi - lo + 1);
    int i = lo, j = mid + 1;
    while (i <= mid && j <= hi) {
      tmp.push_back(v[i] <= v[j] ? v[i++] : v[j++]);
    }
    while (i <= mid) tmp.push_back(v[i++]);
    while (j <= hi) tmp.push_back(v[j++]);
    for (int k = 0; k < (int)tmp.size(); ++k) v[lo + k] = tmp[k];
  }
};

You wrote this in 342 chapter 14. This chapter names the paradigm: divide and conquer.

34.2 Learning objectives

  1. Decompose a problem into divide, conquer, and combine steps.
  2. Write a recurrence relation for a given recursive algorithm.
  3. Apply the Master Theorem to classify the recurrence.
  4. Implement Merge k Sorted Lists using D&C with a min-heap.
  5. Explain why D&C beats brute force through subproblem independence.

34.3 The paradigm

  1. Divide: split the problem into smaller subproblems.
  2. Conquer: solve each subproblem recursively.
  3. Combine: merge the subproblem solutions into the answer.

Merge sort:

  1. Divide: split into halves.
  2. Conquer: sort each half.
  3. Combine: merge two sorted halves.

Binary search:

  1. Divide: half the search range.
  2. Conquer: search the appropriate half.
  3. Combine: trivial — return whatever the half returned.

34.4 Recurrence relations

A recurrence describes the cost in terms of subproblem costs.

Algorithm Recurrence Complexity
Binary search T(n) = T(n/2) + O(1) O(log n)
Merge sort T(n) = 2T(n/2) + O(n) O(n log n)
Quicksort (average) T(n) = 2T(n/2) + O(n) O(n log n)
Quicksort (worst) T(n) = T(n-1) + O(n) O(n²)
Naive Fibonacci T(n) = T(n-1) + T(n-2) + O(1) O(2ⁿ)

34.5 The Master Theorem

For recurrences of the form T(n) = aT(n/b) + f(n):

Case Condition Result
1 f(n) = O(n^c), c < log_b a T(n) = Θ(n^(log_b a))
2 f(n) = Θ(n^(log_b a)) T(n) = Θ(n^(log_b a) · log n)
3 f(n) = Ω(n^c), c > log_b a T(n) = Θ(f(n))

Examples:

  • Merge sort: a=2, b=2, log_b a = 1. f(n) = O(n) = Θ(n^1). Case 2. T(n) = Θ(n log n). ✓
  • Binary search: a=1, b=2, log_b a = 0. f(n) = O(1) = Θ(n^0). Case 2. T(n) = Θ(log n). ✓
  • T(n) = 8T(n/2) + O(n²): a=8, b=2, log_b a = 3. f(n) = n² = O(n^c) with c=2 < 3. Case 1. T(n) = Θ(n³). (Strassen’s matrix multiplication recurrence is T(n) = 7T(n/2) + O(n²), giving Θ(n^log₂7) ≈ Θ(n^2.807) — beating the naive O(n³).)

The Master Theorem is a calculator. Memorize the three cases on a flashcard. You will use it every time you analyze a D&C algorithm.

34.6 Merge k sorted lists

Given k sorted lists with N total elements, merge them into one sorted list.

34.6.1 Naive: pairwise merge

Merge list 0 with list 1, then merge result with list 2, etc.

ListNode* mergeKLists(vector<ListNode*>& lists) {
  ListNode* result = nullptr;
  for (auto* l : lists) result = merge(result, l);
  return result;
}

After merging i lists the result has size proportional to (N · i / k). Total work: O(N · k). Bad.

34.6.2 D&C: pairwise but smarter

Merge in pairs: list 0 with 1, list 2 with 3, …, then merge the resulting k/2 lists pairwise, etc.

ListNode* mergeKLists(vector<ListNode*>& lists) {
  if (lists.empty()) return nullptr;
  while (lists.size() > 1) {
    vector<ListNode*> next;
    for (int i = 0; i + 1 < (int)lists.size(); i += 2) {
      next.push_back(merge(lists[i], lists[i+1]));
    }
    if (lists.size() % 2 == 1) next.push_back(lists.back());
    lists = next;
  }
  return lists[0];
}

T(N) = 2T(N/2) + O(N) for the merge. Same recurrence as merge sort: O(N log k).

34.6.3 Min-heap approach

Push the head of each list into a min-heap. Repeatedly pop the smallest and push its next pointer.

ListNode* mergeKLists(vector<ListNode*>& lists) {
  auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
  priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
  for (auto* l : lists) if (l) pq.push(l);

  ListNode dummy(0);
  ListNode* tail = &dummy;
  while (!pq.empty()) {
    ListNode* cur = pq.top();
    pq.pop();
    tail->next = cur;
    tail = cur;
    if (cur->next) pq.push(cur->next);
  }
  return dummy.next;
}

Each push/pop is O(log k). N elements total. O(N log k), same as D&C version. Easier to write correctly.

34.7 Try it

Implement quickselect — find the k-th smallest element of an unsorted array in expected O(n).

Pick a random pivot. Partition. Recurse only into the side containing the k-th. The recurrence is T(n) = T(n/2) + O(n) on average, giving O(n).

34.8 Self-check

1. T(n) = 4T(n/2) + n². By Master Theorem, T(n) =
b. a=4, b=2, log_b a = 2. f(n) = n² = Θ(n²). Case 2 ⇒ Θ(n² log n).
2. Naive merge-k-sorted-lists pairwise is O(N · k). The D&C version is:
c. Same recurrence as merge sort with the parameter being k lists.

34.9 Challenges

  1. Merge k Sorted Lists (#23).
  2. Kth Largest Element in an Array (#215) — quickselect.
  3. Pow(x, n) (#50) — O(log n) recursive power.
  4. Count of Smaller Numbers After Self (#315) — merge sort variant.

34.10 Where this fits

D&C is the first of three algorithm design paradigms we cover. Next: greedy.

You are here Coming up
D&C paradigm, Master Theorem, merge k lists Chapter 32: greedy algorithms