CMPT 225 Lecture Notes - Lecture 8: Merge Sort, Heapsort, Quicksort

• School: Simon Fraser University
• Department: Computing Science
• Course: CMPT 225
• Professor: David Mitchell

Document Summary

Note: in quicksort, partition does all of the work, in merge sort, merge does all the work. Let t(n) be running time on n elements. The recurrence for t depends on the rank of the pivot. T(n) = t(rank -1) + t(n-rank-1) + o(n) (sorting nearly sorted lists is common, so selecting pirvot position as last takes long time, specifically o(n2) T(n) <= t(n/2) + t(n/2) + o(n) = o(nlogn), like merge and heap sort. If we pick pivots uniformly at random from a, we get t(n) = o(nlogn) on average (very high probability of this) Intuition: getting a few bad pivots is ok, getting many bad pivots is unlikely. Sorting in practice: quicksort is default, not hard to choose pivots that are not bad very often. But, if n is very small, selection sort is faster (it is simplt) and does less work overall. Stores a set of keys (values from some ordered set) eg ints, strings, records.