Divide & Conquer: Merging, Sorting, and the Master Theorem

Core Philosophy

Divide & Conquer is a strategy centered on three recursive steps:

1. Divide: Break the problem into several sub-problems that are smaller instances of the same problem.
2. Conquer: Address the sub-problems recursively. If they are small enough (base case), solve them directly.
3. Combine: Merge the solutions of the sub-problems to form the solution to the original problem.

[!NOTE] Unlike general recursion, Divide & Conquer specifically requires that sub-problems are independent and share the same structure as the parent problem.

Merge Sort: The Canonical Example

A stable, $O(N \log N)$ sorting algorithm that embodies the "Combine" logic.

public void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return; // Base Case
    int mid = left + (right - left) / 2;
    
    mergeSort(arr, left, mid);      // Divide Left
    mergeSort(arr, mid + 1, right); // Divide Right
    merge(arr, left, mid, right);   // Combine
}

private void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    
    while (i <= mid && j <= right) {
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    
    System.arraycopy(temp, 0, arr, left, temp.length);
}

Quick Sort: Partition-based Divide & Conquer

Quick sort focuses on the "Divide" step through Partitioning.

public void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivotIndex = partition(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
}

private int partition(int[] arr, int left, int right) {
    int pivot = arr[right]; // Choosing last element as pivot
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            swap(arr, ++i, j);
        }
    }
    swap(arr, i + 1, right);
    return i + 1;
}

Complexity: Average $O(N \log N)$, Worst-case $O(N^2)$ (on sorted arrays with fixed pivots). Optimization: Randomized pivot selection or "Median-of-Three" can prevent worst-case scenarios.

Master Theorem

Use this for quick asymptotic analysis of Divide & Conquer recurrences:

$$T(n) = aT(n/b) + f(n)$$

• $a \ge 1$: Number of sub-problems.
• $n/b$: Size of each sub-problem.
• $f(n)$: Cost of of non-recursive work (divide + combine).

Advanced Applications

1. Count Inversions

Calculate the number of pairs $(i, j)$ such that $i < j$ and $arr[i] > arr[j]$.

• Strategy: During the merge step of Merge Sort, if arr[i] > arr[j], then all elements from $i$ to $mid$ are in inversion with arr[j].
• Logic: count += (mid - i + 1).

2. Closest Pair of Points

Find two points with the minimum distance among $N$ points in $O(N \log N)$ time by recursively splitting the plane and checking the "strip" near the mid-line.

Divide & Conquer vs. Dynamic Programming

Technical Proficiency Checklist

• LeetCode 148 (Sort List): Merge sort on Linked Lists.
• LeetCode 23 (Merge K Sorted Lists): Divide and Conquer vs. Priority Queue.
• LeetCode 53 (Maximum Subarray): Handling the "crosses-the-midpoint" case.
• LeetCode 315 (Count of Smaller Numbers After Self): Advanced merge sort technique. 筋