Divide and Conquer · Algorithms (DAA)

Divide and conquer solves a problem in three steps:

Divide the problem into smaller subproblems of the same kind.
Conquer the subproblems recursively (solve tiny ones directly).
Combine the sub-solutions into a solution for the original problem.

Its running time naturally forms a recurrence T(n) = a·T(n/b) + D(n) + C(n), where D and C are the costs of dividing and combining — tailor-made for the Master Theorem.

Binary search

Divide: compare with the middle element — O(1).
Conquer: search one half.
Combine: nothing.

T(n) = T(n/2) + O(1) → Θ(log n).

Merge sort

Divide: split at the middle — O(1).
Conquer: sort both halves recursively.
Combine: merge two sorted halves — Θ(n).

T(n) = 2T(n/2) + Θ(n) → Θ(n log n) in every case.

C++

#include <iostream>
#include <vector>
using namespace std;

long comparisons = 0;

void merge(vector<int> &a, int lo, int mid, int hi) {
    vector<int> left(a.begin() + lo, a.begin() + mid + 1), right(a.begin() + mid + 1, a.begin() + hi + 1);
    size_t i = 0, j = 0;
    int k = lo;
    while (i < left.size() && j < right.size()) {
        comparisons++;
        a[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
    }
    while (i < left.size()) a[k++] = left[i++];
    while (j < right.size()) a[k++] = right[j++];
}

void mergeSort(vector<int> &a, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);
    mergeSort(a, mid + 1, hi);
    merge(a, lo, mid, hi);
}

int main() {
    vector<int> a = {38, 27, 43, 3, 9, 82, 10, 19};
    mergeSort(a, 0, (int)a.size() - 1);
    for (int x : a) cout << x << " ";
    cout << "\ncomparisons: " << comparisons << " (n log2 n = 24)" << endl;
    return 0;
}

Output

3 9 10 19 27 38 43 82 
comparisons: 17 (n log2 n = 24)

Try it Yourself

The divide phase of merge sort on 8 elements: log₂ 8 = 3 levels of splitting. Merging then climbs back up, doing n work per level.

Quick sort

Divide: partition around a pivot — Θ(n). After partitioning, the pivot is in its final position.
Conquer: sort the two parts recursively.
Combine: nothing.

Case	Partition split	Recurrence	Time
Best	always in half	T(n) = 2T(n/2) + n	Θ(n log n)
Worst	always 0 and n − 1 (sorted input, first/last pivot)	T(n) = T(n − 1) + n	Θ(n²)
Average	random splits	—	Θ(n log n), about 1.39 n log₂ n comparisons

Even a consistently lopsided 9-to-1 split gives T(n) = T(9n/10) + T(n/10) + n = Θ(n log n). Only extreme imbalance hurts.

Randomised quick sort

Picking the pivot uniformly at random makes the expected running time Θ(n log n) for every input — no specific input can trigger the worst case reliably.

C++

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
using namespace std;

mt19937 rng(42);
long comparisons;

int partition(vector<int> &a, int lo, int hi) {           // Lomuto, pivot at a[hi]
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++) {
        comparisons++;
        if (a[j] < pivot) swap(a[++i], a[j]);
    }
    swap(a[i + 1], a[hi]);
    return i + 1;
}

void quickSort(vector<int> &a, int lo, int hi, bool randomPivot) {
    if (lo >= hi) return;
    if (randomPivot) swap(a[uniform_int_distribution<int>(lo, hi)(rng)], a[hi]);
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1, randomPivot);
    quickSort(a, p + 1, hi, randomPivot);
}

int main() {
    int n = 2000;
    vector<int> sortedInput(n);
    for (int i = 0; i < n; i++) sortedInput[i] = i;

    vector<int> a = sortedInput;
    comparisons = 0; quickSort(a, 0, n - 1, false);
    cout << "last-element pivot on sorted input: " << comparisons << " comparisons (about n^2/2)" << endl;

    a = sortedInput;
    comparisons = 0; quickSort(a, 0, n - 1, true);
    cout << "random pivot on sorted input:       " << comparisons << " comparisons (about 1.39 n log2 n)" << endl;
    cout << "still sorted correctly: " << boolalpha << is_sorted(a.begin(), a.end()) << endl;
    return 0;
}

Output

last-element pivot on sorted input: 1999000 comparisons (about n^2/2)
random pivot on sorted input:       22963 comparisons (about 1.39 n log2 n)
still sorted correctly: true

Try it Yourself

Merge sort vs quick sort

	Merge sort	Quick sort
Worst case	Θ(n log n)	Θ(n²) (rare with random pivots)
Extra space	Θ(n)	Θ(log n) stack
Stable	yes	no
Work happens in	the combine step	the divide step
In practice	linked lists, external sorting	arrays in memory (fast, cache-friendly)

Test yourself

4 questions · pick an answer to check it instantly

1
In merge sort, which step does the real work?
2
What is the worst-case recurrence of quick sort?
3
Why use a random pivot?
4
Which sort is preferred for sorting a linked list?

#Binary search

#Merge sort

#Quick sort

#Randomised quick sort

#Merge sort vs quick sort

Test yourself

Binary search

Merge sort

Quick sort

Randomised quick sort

Merge sort vs quick sort