Source code online books for professionals by professionals

Listing 6-1.  A General Implementation of the Divide-and-Conquer Scheme
def divide_and_conquer(S, divide, combine):
    if len(S) == 1: return S
    L, R = divide(S)
    A = divide_and_conquer(L, divide, combine)
    B = divide_and_conquer(R, divide, combine)
    return combine(A, B) 
Figure 
6-5
 is another illustration of the same pattern. The upper half of the figure represents the recursive calls, 
while the lower half represents the way return values are combined. Some algorithms (such as quicksort, described 
later in this chapter) do most of their work in the upper half (division), while some are more active in the lower 
(combination). The perhaps most well-known example of an algorithm with a focus on combination is merge sort 
(described a bit later in this chapter), which is also a prototypical example of a divide-and-conquer algorithm.