Divide and conquer
From Citizendium, the Citizens' Compendium
The divide and conquer algorithmic method refers to the process of taking input data and dividing them into smaller portions (usually halves) and then recursively performing the division on the separate parts until a base with a predefined constant size is reached and some preset algorithm can be performed on the base sized input. The algorithm then performs some function on the separate parts which have already been processed by the recursive calls until it ultimately is able to perform this function on the first division which it performed on the input. Each set of recursive calls deals with the same input (in different divisions) for a running time of O(n) and there are log n divisions so the final running time is O(n log n).
