Divide and conquer

Applies to: general

Divide and conquer solves a problem by splitting it into smaller subproblems, solving those (often recursively), and combining the results. Mergesort, quicksort, and binary search all use it, frequently giving O(n log n) or O(log n).

sort(a) = merge( sort(left half), sort(right half) )

See also: recursion, sorting, binary-search