Randomizing, lower bounds on comparison sorts, counting sort, radix sort, bucket sort.
Heapsort, Quicksort, Mergesort.
Basic ideas about quicksort
Screencast Suthers 24 min
Randomizing and analyzing quicksort
Screencast Suthers 23 min
Lower bounds on comparison sorts, and O(n) sorts
Screencast Suthers 20 min
Description and performance of quicksort, a randomized version, and analysis.
Textbook 20 pages
Lower bounds for sorting, counting sort, radix sort, bucket sort.
Textbook 22 pages
Notes on quicksort
Notes
Learn about quicksort (at home).
Homework