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
Part I – The Basics
- Video 4-0 (2025-11-03):
§4.0 Sorting introduction
- Video 4-1 (2025-11-03):
§4.1 Mergesort
- Video 4-2 (2025-11-04):
§4.2 Quicksort
- Video 4-3 (2025-11-05):
§4.3 Comparison-based lower bound
- Video 4-4 (2025-11-05):
§4.4 Integer sorting
Part II – Exploiting presortedness
- Video 4-5 (2025-11-05):
§4.5 Adaptive sorting
- Video 4-6 (2025-11-10):
§4.5 Adaptive sorting & Peeksort
- Video 4-7 (2025-11-10):
§4.6 Python’s list sort & Powersort
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).