Divide and Conquer

Concept

Divide and conquer splits a problem into smaller subproblems, solves each recursively, then combines the results. The three steps are: divide (split), conquer (recurse), combine (merge). Merge sort is the classic example — split the array in half, sort each half, merge the sorted halves.

When to Use

  • ▸Merge sort — O(n log n) sorting
  • ▸Counting inversions in an array
  • ▸Closest pair of points
  • ▸Problems where splitting in half and combining is natural
  • ▸When brute force is O(n^2) and splitting gives O(n log n)

Intuition

Imagine sorting a deck of cards. Split it into two halves, sort each half separately, then merge them by comparing the top cards of each pile. Each split halves the problem, and merging is linear. With log n levels of splitting and O(n) work per level, total work is O(n log n). The power of divide and conquer: turning a hard big problem into easy small problems plus a cheap combine step.

Complexity

Time
O(n log n) for merge sort
Space
O(n) for merge sort

Template Code

cpp
#include<bits/stdc++.h>
using namespace std;

void merge(vector<int> &v, int l, int mid, int r){
    vector<int> tmp;
    int i = l, j = mid+1;

    while(i <= mid && j <= r){
        if(v[i] <= v[j]) tmp.push_back(v[i++]);
        else tmp.push_back(v[j++]);
    }

    while(i <= mid) tmp.push_back(v[i++]);
    while(j <= r) tmp.push_back(v[j++]);

    for(int i = l; i <= r; i++){
        v[i] = tmp[i-l];
    }
}

void mergeSort(vector<int> &v, int l, int r){
    if(l >= r) return;

    int mid = l + (r - l)/2;
    mergeSort(v, l, mid);
    mergeSort(v, mid+1, r);
    merge(v, l, mid, r);
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n;
    cin >> n;

    vector<int> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];

    mergeSort(v, 0, n-1);

    for(int i = 0; i < n; i++) cout << v[i] << " ";
    cout << "\n";

    return 0;
}

// Sample Input:
// 8
// 5 2 8 1 9 3 7 4
//
// Sample Output:
// 1 2 3 4 5 7 8 9