Divide and conquer (computer science)
From Academic Kids

In computer science, divide and conquer (D&C) is an important algorithm design paradigm. It works by recursively breaking down a problem into two or more subproblems of the same (or related) type, until these become simple enough to be solved directly. The solutions to the subproblems are then combined to give a solution to the original problem.
This technique is the basis of efficient algorithms for all kinds of problems, such as sorting (quicksort, merge sort) and the discrete Fourier transform (FFTs).
Contents 
Implementation
Divideandconquer algorithms are naturally implemented as recursive procedures. In that case, the partial subproblems leading to the one currently being solved in implicitly stored in the procedure call stack.
However, D&C solutions can also be implemented by a nonrecursive algorithm that stores the partial subproblems in some explicit data structure, such as a stack, queue, or priority queue. This approach allows more freedom in the choice of the subproblem that is to be solved next, a feature that is important in some applications — e.g. in breadthfirst recursion and the branch and bound method for function optimization.
Advantages
Solving difficult problems
Divide and conquer is a powerful tool for solving conceptually difficult problems, such as the classic Tower of Hanoi puzzle: all it requires is a way of breaking the problem into subproblems, of solving the trivial cases and of combining subproblems to to the original problem. Dividing the problem into subproblems so that the subproblems can be combined again is often the major difficulty in designing a new algorithm. Indeed, for many such problems the paradigm offers the only simple solution.
Algorithm efficiency
Moreover, divide and conquer often provides a natural way to design efficient algorithms.
For example, if the work of splitting the problem and combining the partial solutions is proportional to the problem's size n, there are a bounded number p of subproblems of size ~ n/p at each stage, and the base cases require O(1) (constantbounded) time, then the divideandconquer algorithm will have O(n log n) complexity. This is used for problems such as sorting and FFTs to reduce the complexity from O(n^{2}), although in general there may also be other approaches to designing efficient algorithms.
Parallelism
Divide and conquer algorithms are naturally adapted for execution in multiprocessor machines, especially sharedmemory systems where the communication of data between processors does not need to be planned in advance, because distinct subproblems can be executed on different processors.
Memory access
Divideandconquer algorithms naturally tend to make efficient use of memory caches. The reason is that once a subproblem is small enough, it and all its subproblems can, in principle, be solved within the cache, without accessing the slower main memory. An algorithm designed to exploit the cache in this way is called cache oblivious, because it does not contain the cache size(s) as an explicit parameter.
Moreover, D&C algorithms can be designed for many important algorithms, such as sorting, FFTs, and matrix multiplication, in such a way as to be optimal cache oblivious algorithms—they use the cache in a provably optimal way, in an asymptotic sense, regardless of the cache size. In contrast, the traditional approach to exploiting the cache is blocking, where the problem is explicitly divided into chunks of the appropriate size—this can also use the cache optimally, but only when the algorithm is tuned for the specific cache size(s) of a particular machine.
The same advantage exists with regards to other hierarchical storage systems, such as NUMA or virtual memory, as well as for multiple levels of cache: once a subproblem is small enough, it can be solved within a given level of the hierarchy, without accessing the higher (slower) levels.
However, the kind of asymptotic optimality described here, analogous to big O notation, ignores constant factors, and additional machine/cachespecific tuning is in general required to achieve optimality in an absolute sense.
Disadvantages
One commonly argued disadvantage of a divideandconquer approach is that recursion is slow: the overhead of the repeated subroutine calls, along with that of storing the call stack (the state at each point in the recursion), can outweigh any advantages of the approach. This, however, depends upon the implementation style: with large enough recursive base cases, the overhead of recursion can become negligible for many problems.
Another problem of a divideandconquer approach is that, for simple problems, it may be more complicated than a iterative approach, especially if large base cases are to be implemented for performance reasons. For example, to add N numbers, a simple loop to add them up in sequence is much easier to code than a divideandconquer approach that breaks the set of numbers into two halves, adds them recursively, and then adds the sums. (On the other hand, the latter approach turns out to be much more accurate in finiteprecision floatingpoint arithmetic.)
Alternatively, an algorithm can be designed by a divideandconquer approach and then implemented in an iterative style; of course, any recursive algorithm can be simulated in an iterative style, but by reordering the computation it is sometimes possible to avoid simulating a recursive call stack altogether. The CooleyTukey FFT algorithm is a prime example of this: it was initially derived in a divideandconquer style, but implementations were traditionally implemented iteratively in a reordered fashion that avoided callstacklike storage (although some recent implementations have returned to a recursive style).
See also
References
 M. Frigo, C. E. Leiserson, and H. Prokop, "Cacheoblivious algorithms (http://theory.lcs.mit.edu/~athena/abstracts/abstract4.html#afterheading)", Proc. 40th Symp. on the Foundations of Computer Science (1999).
 Nicholas J. Higham, "The accuracy of floating point summation", SIAM J. Scientific Computing 14 (4), 783–799 (1993).de:Teile und herrsche
fr:Diviser pour régner (informatique) he:אלגוריתם הפרד ומשול sl:deli in vladaj (računalništvo) zh:分治法