Divide and Conquer: Merge Sort, Quicksort, and Master Theorem

The Core Concept

Divide & Conquer is a process of splitting, recurring, and combining.

The Three Steps:
1. Divide   — Break the problem into smaller, independent subproblems of the same type.
2. Conquer  — Solve subproblems recursively (base case: direct solution for small input).
3. Combine  — Merge subproblem solutions to form the original answer.

Comparison: Unlike standard recursion, Divide & Conquer emphasizes that subproblems are mutually independent and structurally identical to the root problem.

Merge Sort: A Pure Divide & Conquer Implementation

public void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return; // Base case: single element
    
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);      // Divide: Left half
    mergeSort(arr, mid + 1, right); // Divide: Right half
    merge(arr, left, mid, right);   // Combine: Merge sorted halves
}

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);
}

• Complexity: $T(n) = 2T(n/2) + O(n) \rightarrow \mathbf{O(N \log N)}$.
• Characteristics: Stable, $O(N)$ extra space for arrays.

Quicksort: In-place Divide & Conquer

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 pivotValue = arr[right]; 
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivotValue) {
            swap(arr, ++i, j);
        }
    }
    swap(arr, i + 1, right);
    return i + 1;
}

• Complexity: Average $O(N \log N)$, Worst $O(N^2)$ (e.g., already sorted array with static pivot).
• Optimizations: Random pivots, 3-way partitioning, fallback to Insertion Sort for small ranges.

The Master Theorem

A formula for quick asymptotic analysis of Divide & Conquer algorithms:

$$T(n) = aT\left(\frac{n}{b}\right) + f(n)$$

• $a$: Number of recursive subproblems.
• $n/b$: Size of each subproblem.
• $f(n)$: Cost of dividing and merging.

Specialized Applications

Counting Inversions

During merge, if arr[i] > arr[j], then all elements from i to mid form an inversion pair with arr[j]. This allows counting inversions in $O(N \log N)$ instead of $O(N^2)$.

Closest Distance Pair

Find the two points with minimum Euclidean distance:

• Naive: $O(N^2)$
• Divide & Conquer: $O(N \log N)$ by solving left/right halves and checking the narrow strip between them.

Karatsuba Multiplier (Large Integers)

Reduces the number of recursive multiplications from 4 to 3 for binary multiplication, achieving $O(n^{1.585})$ complexity.

Divide & Conquer vs. Dynamic Programming

Core Optimization Practice