NIST

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.

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

Authors: PEB,CM

More information

Three divide and conquer sorting algorithms.


Go to the Dictionary of Algorithms and Data Structures home page.

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