Divide and Conquer in the Real World

In C++, std::nth_element puts the k-th element in its sorted position and partitions the rest around it in linear time on average:

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{9, 1, 8, 2, 7, 3};
    std::nth_element(v.begin(), v.begin() + 2, v.end());
    std::cout << v[2] << '\n';  // 3, the third smallest
}

Common pitfalls

• Recursion depth: Python's default limit is about 1000 frames. Balanced splits only go log n deep, but a split that removes one element at a time (a bad pivot, a skewed tree) can overflow. Prefer loops for decrease-and-conquer and random pivots for quickselect.
• Hidden copying: a[:mid] copies half the list. Slicing at every level is still O(n log n) overall, but it allocates heavily; pass index ranges and reuse one buffer when speed matters.
• Tiny subproblems: function calls are expensive compared with a few comparisons. Real sorts switch to insertion sort below a small cutoff, and Karatsuba falls back to schoolbook multiplication for small numbers.
• Off-by-one splits: decide whether ranges are half-open [lo, hi) or closed [lo, hi] and stick to it. In a binary search with mid = (lo + hi) // 2, the update lo = mid never moves on a two-element range, so the loop runs forever.
• Overflow: in C++, Java and JavaScript, multiplying two residues can exceed 64 bits or 2^53; see the implementation chapter.
• Equal keys: Lomuto partitioning degrades to O(n^2) when all values are equal. Use a three-way partition, as in the practice problems.

Avoiding recursion: bottom-up merge sort

Merge sort can also run without recursion by merging runs of width 1, 2, 4 and so on:

def merge_sort_bottom_up(a):
    a = list(a)
    n, width = len(a), 1
    while width < n:
        for lo in range(0, n, 2 * width):
            mid, hi = min(lo + width, n), min(lo + 2 * width, n)
            left, right = a[lo:mid], a[mid:hi]
            i = j = 0
            for k in range(lo, hi):
                if j == len(right) or (i < len(left) and left[i] <= right[j]):
                    a[k] = left[i]
                    i += 1
                else:
                    a[k] = right[j]
                    j += 1
        width *= 2
    return a

print(merge_sort_bottom_up([5, 2, 4, 7, 1, 3, 2, 6]))  # [1, 2, 2, 3, 4, 5, 6, 7]

This is also the shape external sorting and parallel merge passes take.

Summary

• Sorting, selection, big-number multiplication, the FFT and modular exponentiation in cryptography are all divide and conquer under the hood.
• Reach for sorted, pow, heapq, std::nth_element or numpy.partition before writing your own.
• When you do implement it, watch recursion depth, copying, small-case cutoffs, overflow and equal keys.

Further reading

• Divide-and-conquer algorithm (Wikipedia)
• Master theorem (Wikipedia)
• Binary Exponentiation (cp-algorithms)
• Finding the nearest pair of points (cp-algorithms)
• Karatsuba algorithm (Wikipedia)
• MIT 6.046J Design and Analysis of Algorithms
• std::nth_element (cppreference)
• Python built-in pow