Lecture Notes CMSC 251 To bound this recall the integration formula for bounding summations which we paraphrase here For any monotonically increasing function f x b 1 X Z f i b f x dx a i a The function f x x ln x is monotonically increasing and so we have Z n x ln xdx S n 2 If you are a calculus macho man then you can integrate this by parts and if you are a calculus wimp like me then you can look it up in a book of integrals 2 Z n n x2 n2 n2 n2 x2 n ln x ln n 2 ln 2 1 ln n x ln xdx 2 4 x 2 2 4 2 4 2 This completes the summation bound and hence the entire proof Summary So even though the worst case running time of QuickSort is n2 the average case running time is n log n Although we did not show it it turns out that this doesn t just happen much of the time For large values of n the running time is n log n with high probability In order to get n2 time the algorithm must make poor choices for the pivot at virtually every step Poor choices are rare and so continuously making poor choices are very rare You might ask could we make QuickSort deterministic n log n by calling the selection algorithm to use the median as the pivot The answer is that this would work but the resulting algorithm would be so slow practically that no one would ever use it QuickSort like MergeSort is not formally an in place sorting algorithm because it does make use of a recursion stack In MergeSort and in the expected case for QuickSort the size of the stack is O log n so this is not really a problem QuickSort is the most popular algorithm for implementation because its actual performance on typical modern architectures is so good The reason for this stems from the fact that unlike Heapsort which can make large jumps around in the array the main work in QuickSort in partitioning spends most of its time accessing elements that are close to one another The reason it tends to outperform MergeSort which also has good locality of reference is that most comparisons are made against the pivot element which can be stored in a register In MergeSort we are always comparing two array elements against each other The most efficient versions of QuickSort uses the recursion for large subarrays but once the sizes of the subarray falls below some minimum size e g 20 it switches to a simple iterative algorithm such as selection sort Lecture 16 Lower Bounds for Sorting Thursday Mar 19 1998 Read Chapt 9 of CLR Review of Sorting So far we have seen a number of algorithms for sorting a list of numbers in ascending order Recall that an in place sorting algorithm is one that uses no additional array storage however we allow QuickSort to be called in place even though they need a stack of size O log n for keeping track of the recursion A sorting algorithm is stable if duplicate elements remain in the same relative position after sorting 52 Lecture Notes CMSC 251 Slow Algorithms Include BubbleSort InsertionSort and SelectionSort These are all simple n2 in place sorting algorithms BubbleSort and InsertionSort can be implemented as stable algorithms but SelectionSort cannot without significant modifications Mergesort Mergesort is a stable n log n sorting algorithm The downside is that MergeSort is the only algorithm of the three that requires additional array storage implying that it is not an in place algorithm Quicksort Widely regarded as the fastest of the fast algorithms This algorithm is O n log n in the expected case and O n2 in the worst case The probability that the algorithm takes asymptotically longer assuming that the pivot is chosen randomly is extremely small for large n It is an almost in place sorting algorithm but is not stable Heapsort Heapsort is based on a nice data structure called a heap which is a fast priority queue Elements can be inserted into a heap in O log n time and the largest item can be extracted in O log n time It is also easy to set up a heap for extracting the smallest item If you only want to extract the k largest values a heap can allow you to do this is O n k log n time It is an in place algorithm but it is not stable Lower Bounds for Comparison Based Sorting Can we sort faster than O n log n time We will give an argument that if the sorting algorithm is based solely on making comparisons between the keys in the array then it is impossible to sort more efficiently than n log n time Such an algorithm is called a comparison based sorting algorithm and includes all of the algorithms given above Virtually all known general purpose sorting algorithms are based on making comparisons so this is not a very restrictive assumption This does not preclude the possibility of a sorting algorithm whose actions are determined by other types of operations for example consulting the individual bits of numbers performing arithmetic operations indexing into an array based on arithmetic operations on keys We will show that any comparison based sorting algorithm for a input sequence ha1 a2 an i must make at least n log n comparisons in the worst case This is still a difficult task if you think about it It is easy to show that a problem can be solved fast just give an algorithm But to show that a problem cannot be solved fast you need to reason in some way about all the possible algorithms that might ever be written In fact it seems surprising that you could even hope to prove such a thing The catch here is that we are limited to using comparison based algorithms and there is a clean mathematical way of characterizing all such algorithms Decision Tree Argument In order to prove lower bounds we need an abstract way of modeling any possible comparison based sorting algorithm we model such algorithms in terms of an abstract model called a decision tree In a comparison based sorting algorithm only comparisons between the keys are used to determine the action of the algorithm Let ha1 a2 an i be the input sequence Given two elements ai and aj their relative order can only be determined by the results of comparisons like ai aj ai aj ai aj ai aj and ai aj A decision tree is a mathematical representation of a sorting algorithm for a fixed value of n Each node of the decision tree represents a comparison made in the algorithm e g a4 a7 and the two branches represent the possible results for example the left subtree consists of the remaining comparisons made under the assumption that a4 a7 and the right subtree for a4 a7 Alternatively one might be labeled with a4 a7 and the other with a4 a7 …