Will look at two approaches. At each point simply divide the list into two and sort each list. We can have no more comparisons than elements being merged. Hence if we look at Figure 7.10 we see a total of n elements at each level and levels for a total of . Thus merge sort is in number of comparisons.
Biggest disadvantage is that it requires an auxilliary array when using array storage.
Quick Sort Use a pivot to divide the list. Pick a pivot in the middle of the list and work through the algorithm shown on pg 248 of Kruse text. Quick Sort is done recursively. However, on average the worst case does not happen and the average case is and unlike merge sort it requires no auxillary array.