main page — CS 566 Efficient Algorithms
Unit 4: Efficient Sorting
This unit covers
- mergesort and quicksort
- counting sort
- comparions lower bound for sorting
- adaptive sorting
Learning outcomes
- Know principles and implementation of mergesort and quicksort.
- Know properties and performance characteristics of mergesort and quicksort.
- Know the comparison model and understand the corresponding lower bound.
- Understand counting sort and how it circumvents the comparison lower bound.
- Know ways how to exploit presorted inputs.
Material
Further reading and sources
More elementary sorting methods are described in detail in Algorithms 4th ed.
- Sedgewick, Wayne: Algorithms 4th ed (2011), Pearson
- Algorithms 4th ed booksite
The exposition of adaptive sorting is my own and based on several sources:
- Tim Peters’s description of CPython’s list.sort algorithm
- Munro, Wild: Nearly Optimal Mergesorts, ESA 2018
- Cawley Gelling, Nebel, Smith, Wild: Multiway Powersort, ALENEX 2023
- Gaurav Sen: Tim sort explained,
Part 1,
Part 2,
Part 3,
Part 4.
Sequence of videos explaining Timsort’s other tricks (prior to adopting powersort’s merge rules).