(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.
See also recursion, greedy algorithm.
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 |
Three divide and conquer sorting algorithms.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 14 June 2010.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black and Conrado Martinez, "divide and conquer", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 14 June 2010. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/divideAndConquer.html