Editing Divide-and-conquer algorithm (section)

== Early historical examples ==
Early examples of these algorithms are primarily decrease and conquer – the original problem is successively broken down into ''single'' subproblems, and indeed can be solved iteratively.

[[Binary search algorithm|Binary search]], a decrease-and-conquer algorithm where the subproblems are of roughly half the original size, has a long history. While a clear description of the algorithm on computers appeared in 1946 in an article by [[John Mauchly]], the idea of using a sorted list of items to facilitate searching dates back at least as far as [[Babylonia]] in 200&nbsp;BC.<ref name=Knuth3/> Another ancient decrease-and-conquer algorithm is the [[Euclidean algorithm]] to compute the [[greatest common divisor]] of two numbers by reducing the numbers to smaller and smaller equivalent subproblems, which dates to several centuries BC.

An early example of a divide-and-conquer algorithm with multiple subproblems is [[Carl Friedrich Gauss|Gauss]]'s 1805 description of what is now called the [[Cooley–Tukey FFT algorithm|Cooley–Tukey fast Fourier transform]] (FFT) algorithm,<ref name=Heideman84>Heideman, M. T., D. H. Johnson, and C. S. Burrus, "[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.331.4791&rep=rep1&type=pdf Gauss and the history of the fast Fourier transform]", IEEE ASSP Magazine, 1, (4), 14–21 (1984).</ref> although he did not [[analysis of algorithms|analyze its operation count]] quantitatively, and FFTs did not become widespread until they were rediscovered over a century later.

An early two-subproblem D&C algorithm that was specifically developed for computers and properly analyzed is the [[merge sort]] algorithm, invented by [[John von Neumann]] in 1945.<ref>{{ cite book | last=Knuth | first=Donald | author-link=Donald Knuth | year=1998 | title=The Art of Computer Programming: Volume 3 Sorting and Searching | url=https://archive.org/details/artofcomputerpro03knut | url-access=limited | page=[https://archive.org/details/artofcomputerpro03knut/page/159 159] | publisher=Addison-Wesley | isbn=0-201-89685-0 }}</ref>

Another notable example is the [[Karatsuba algorithm|algorithm]] invented by [[Anatolii Alexeevitch Karatsuba|Anatolii A. Karatsuba]] in 1960<ref>{{cite journal| last=Karatsuba | first=Anatolii A. | author-link=Anatolii Alexeevitch Karatsuba |author2=Yuri P. Ofman |author-link2=Yuri Petrovich Ofman | year=1962 | title=Умножение многозначных чисел на автоматах | journal=[[Doklady Akademii Nauk SSSR]] | volume=146 | pages=293–294}} Translated in {{cite journal| title=Multiplication of Multidigit Numbers on Automata | journal=Soviet Physics Doklady | volume=7 | year=1963 | pages=595–596 | bibcode=1963SPhD....7..595K |url={{Google books|MrkOAAAAIAAJ|plainurl=true}} | last1=Karatsuba | first1=A. | last2=Ofman | first2=Yu. }}</ref> that could multiply two ''n''-[[Units of information|digit]] numbers in <math>O(n^{\log_2 3})</math> operations (in [[Big O notation]]). This algorithm disproved [[Andrey Kolmogorov]]'s 1956 conjecture that <math>\Omega(n^2)</math> operations would be required for that task.

As another example of a divide-and-conquer algorithm that did not originally involve computers, [[Donald Knuth]] gives the method a [[post office]] typically uses to route mail: letters are sorted into separate bags for different geographical areas, each of these bags is itself sorted into batches for smaller sub-regions, and so on until they are delivered.<ref name=Knuth3>Donald E. Knuth, ''The Art of Computer Programming: Volume 3, Sorting and Searching'', second edition (Addison-Wesley, 1998).</ref> This is related to a [[radix sort]], described for [[IBM 80 series Card Sorters|punch-card sorting]] machines as early as 1929.<ref name=Knuth3/>