Next: Randomization Up: Approaches to Sorting Previous: Incremental Insertion

## Divide and Conquer

Suppose we take the n elements to sort and split them into piles S and T, each with half the elements. After sorting both piles, it is easy to combine the two sorted piles. To merge and , note that the smallest item must sit at the top of one of the two lists. Once identified, the smallest element can be removed, and the second smallest item will again be atop one of the two lists. Repeating this operation merges the two sorted lists in O(n) time. This provides the basis for a recursive algorithm.

```

Mergesort(A[1,n])

Merge( MergeSort(  ), MergeSort(  ) )

```

Because the recursion goes levels deep and a linear amount of work is done per level, Mergesort takes time in the worst case.

Mergesort is a classic divide-and-conquer algorithm. Whenever we can break one large problem into two smaller problems, we are ahead of the game because the smaller problems are easier. The trick is taking advantage of the two partial solutions to put together a solution of the full problem. The merge operation takes care of the reassembly in mergesort, but not all problems can be so neatly decomposed.

Algorithms
Mon Jun 2 23:33:50 EDT 1997