next up previous contents index CD CD Algorithms
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 tex2html_wrap_inline24064 and tex2html_wrap_inline24066 , 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.   


Merge( MergeSort( tex2html_wrap_inline24072 ), MergeSort( tex2html_wrap_inline24074 ) )

Because the recursion goes tex2html_wrap_inline24076 levels deep and a linear amount of work is done per level, Mergesort takes tex2html_wrap_inline24078 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.

Mon Jun 2 23:33:50 EDT 1997