Divide and conquer guide · 6/6

Divide and Conquer in the Real World

Divide and conquer is rarely something you write from scratch at work, but it runs inside many tools you use every day. This chapter shows where it appears, which library functions to reach for, and the mistakes that show up when you implement it yourself.

Where it shows up

Sorting libraries: Python's list.sort and Java's Arrays.sort for objects use Timsort, a merge-based sort; Java sorts primitive arrays with dual-pivot quicksort. std::stable_sort in C++ is typically a merge sort and std::sort an introsort (quicksort that falls back to heapsort).
Selection: std::nth_element in C++ and numpy.partition (introselect by default) are quickselect variants with protection against bad pivots.
Big-number arithmetic: CPython multiplies large integers with Karatsuba once they exceed a size threshold, and libraries such as GMP switch to Toom-Cook and FFT-based methods for even larger numbers.
Signal processing: the Cooley-Tukey FFT splits a transform of size n into two of size n/2, turning O(n^2) into O(n log n).
Cryptography: RSA and Diffie-Hellman depend on modular exponentiation with exponents of thousands of bits, which is only feasible with fast power.
Databases and big data: when data does not fit in memory, external merge sort writes sorted runs to disk and merges them. Sort-merge joins, MapReduce-style jobs and Java's fork/join framework all split work, process the parts independently, and combine the results.
Debugging: git bisect binary-searches the commit history to find the change that introduced a bug.

Use the library first

import heapq
import statistics

MOD = 1_000_000_007
print(pow(3, 10**18, MOD))        # built-in fast modular power
print(pow(3, -1, MOD))            # modular inverse (Python 3.8+)

data = [9, 1, 8, 2, 7, 3]
print(heapq.nsmallest(2, data))   # [1, 2], O(n log k)
print(statistics.median(data))    # 5.0
print(sorted(data))               # Timsort, stable, O(n log n)

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.