I&C SCI 46 Lecture Notes - Lecture 17: Merge Sort, Sorting Algorithm, Binary Logarithm

• School: UC-Irvine
• Department: Information and Computer Science
• Course: I&C SCI 46
• Professor: Richard Pattis

Document Summary

Sorting: o(n log2 n) sorts and lower bounds. In this lecture we will discuss three o(n log2 n) sorting algorithms (although for quicksort, this bound is the average case, not the worst case). We will also discuss a non-trivial lower bound for sorting (to me, this is especially interesting and surprising). Nxo(log2 n) + nxo(log2 n) = 2nxo(log2 n) = o(n log2 n). The complexity of the offline algorithm is o(n) + nxo(log2 n) = o(n+nlog2 n) = o(n log2 n). It takes this amount of work even in the best case. 2) in-place (all data is stored in the array that is the heap); when we remove values (biggest first) we swap it with the last used location in the array, and then do not use that location any more. The result at the end is an array filled in sorted order. 3) o(n log2 n) comparisons; o(n log2 n) swaps in the worst case.