 # divide and conquer

(algorithmic technique)

Definition: Solve a problem, either directly because solving that instance is easy (typically, because the instance is small) or by dividing it into two or more smaller instances. Each of these smaller instances is recursively solved, and the solutions are combined to produce a solution for the original instance.

Specialization (... is a kind of me.)
easy split, hard merge, hard split, easy merge.

Aggregate parent (I am a part of or used in ...)
heapify, merge sort, quicksort, binary search.

Note: The technique is named "divide and conquer" because a problem is conquered by dividing it into several smaller problems.

This technique yields elegant, simple and quite often very efficient algorithms. Well-known examples include heapify, merge sort, quicksort, Strassen's fast matrix multiplication, fast multiplication (in O(n log n log log n), see E. A. Karatsuba's Fast Algorithms), the Fast Fourier Transform (FFT), and binary search. (Why is binary search included? The dividing part picks which segment to search, and "the solutions are combined" trivially: take the answer from the segment searched. Segments not searched are "recursively solved" by the null operation: they are ignored.) A similar principle is at the heart of several important data structures such as binary search tree, multiway search trees, tries, skip lists, multidimensional search trees (k-d trees, quadtrees), etc.

Here is the translation of "divide and conquer" in different languages:

 French diviser pour régner German teile und herrsche Latin divide et impera Spanish divide y vencerás

Authors: PEB,CM