Divide-and-conquer

It first splits the problem into subproblems that are easier to solve than the original, either because they are smaller instances of the original problem, or because they are different but easier problems. Next, the algorithm solves the subproblems recursively. These subproblems can be solved independently. Finally, the solutions are merged to construct the original algorithm. It is also possible to divide the original problem in many steps and then solve them all in parallel.

As an example of divide-and-conquer, consider the sequential mergesort algorithm. It takes $n$ number of input keys and returns the keys in sorted order. It works on splitting the keys to two sets of $n/2$ keys, recursively sorting each set, and merging the two sorted sets into a single set of sorted keys. The running time of the algorithm is given according to recurrence rule as follows:

$$T(n) = \begin{cases} 2T(n/2) + O(n), n > 1\\ O(n), ~~~~~~~~~~~~~~~n=1.\\ \end{cases}$$

The above has solution of $T(n) = O(n\log n)$. Although not designed as a parallel algorithm, mergesort has some inherent parallelism since the two recursive calls can be made in parallel. This can be expressed as:

ALGORITHM: MERGESORT(A).

if($\vert A\vert$ = 1) then return A

else

    in parallel do

      L:= MERGESORT( $A[0..\vert A\vert/2$)

      R:= MERGESORT( $A[\vert A\vert/2+1 .. [A]]$)

return MERGE(L, R)