Lecture Notes CMSC 251To bound this, recall the integration formula for bounding summations (which we paraphrasehere). For any monotonically increasing function f(x)b−1Xi=af(i) ≤Zbaf(x)dx.The function f(x)=xln x is monotonically increasing, and so we haveS(n) ≤Zn2x ln xdx.If you are a calculus macho man, then you can integrate this by parts, and if you are a calculuswimp (like me) then you can look it up in a book of integralsZn2x ln xdx =x22ln x −x24nx=2=n22ln n −n24− (2 ln 2 − 1) ≤n22ln n −n24.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 runningtime is Θ(n log n). Although we did not show it, it turns out that this doesn’t just happen much ofthe 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 arerare, and so continuously making poor choices are very rare. You might ask, could we make QuickSortdeterministic Θ(n log n) by calling the selection algorithm to use the median as the pivot. The answeris that this would work, but the resulting algorithm would be so slow practically that no one would everuse it.QuickSort (like MergeSort) is not formally an in-place sorting algorithm, because it does make use of arecursion 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 typicalmodern architectures) is so good. The reason for this stems from the fact that (unlike Heapsort) whichcan make large jumps around in the array, the main work in QuickSort (in partitioning) spends most ofits 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 againsteach other. The most efficient versions of QuickSort uses the recursion for large subarrays, but oncethe sizes of the subarray falls below some minimum size (e.g. 20) it switches to a simple iterativealgorithm, 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 ascendingorder. 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 keepingtrack of the recursion). A sorting algorithm is stable if duplicate elements remain in the same relativeposition after sorting.52Lecture Notes CMSC 251Slow Algorithms: Include BubbleSort, InsertionSort, and SelectionSort. These are all simple Θ(n2)in-place sorting algorithms. BubbleSort and InsertionSort can be implemented as stable algo-rithms, but SelectionSort cannot (without significant modifications).Mergesort: Mergesort is a stable Θ(n log n) sorting algorithm. The downside is that MergeSort isthe only algorithm of the three that requires additional array storage, implying that it is not anin-place algorithm.Quicksort: Widely regarded as the fastest of the fast algorithms. This algorithm is O(n log n) in theexpected case, and O(n2) in the worst case. The probability that the algorithm takes asymptoti-cally longer (assuming that the pivot is chosen randomly) is extremely small for large n.Itisan(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 inO(log n) time. (It is also easy to set up a heap for extracting the smallest item.) If you only wantto extract the k largest values, a heap can allow you to do this is O(n + k log n) time. It is anin-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 anargument that if the sorting algorithm is based solely on making comparisons between the keys in thearray, then it is impossible to sort more efficiently than Ω(n log n) time. Such an algorithm is called acomparison-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 isnot a very restrictive assumption. This does not preclude the possibility of a sorting algorithm whoseactions are determined by other types of operations, for example, consulting the individual bits ofnumbers, performing arithmetic operations, indexing into an array based on arithmetic operations onkeys.We will show that any comparison-based sorting algorithm for a input sequence ha1,a2,...,animustmake 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 problemcannot be solved fast you need to reason in some way about all the possible algorithms that might everbe written. In fact, it seems surprising that you could even hope to prove such a thing. The catch hereis that we are limited to using comparison-based algorithms, and there is a clean mathematical way ofcharacterizing all such algorithms.Decision Tree Argument: In order to prove lower bounds, we need an abstract way of modeling “any pos-sible” comparison-based sorting algorithm, we model such algorithms in terms of an abstract modelcalled a decision tree.In a comparison-based sorting algorithm only comparisons between the keys are used to determinethe action of the algorithm. Let ha1,a2,...,anibe the input sequence. Given two elements, aiandaj, 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). Eachnode of the decision tree represents a comparison made in the algorithm (e.g., a4: a7), and the twobranches represent the possible results, for example, the left subtree consists of the remaining compar-isons made under the