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
- slides
- Mergesort
- Quicksort
- Mergesort with sorted check
- Peeksort
- Powersort’s Pursuit (Mergesort Game)
- Powersort
- Video 4-0 · transcript (2026-11-02, 10:01): Sorting Intro
- Video 4-1 · transcript (2026-11-02, 14:46): Mergesort
- Video 4-2 · transcript (2026-11-03, 24:07): Quicksort
- Video 4-3 · transcript (2026-11-03, 24:11): Comparison-Based Lower Bound
- Video 4-4 · transcript (2026-11-03, 15:12): Integer Sorting
- Video 4-5 · transcript (2026-11-03, 14:30): Mergesort with sorted check
- Video 4-6 · transcript (2026-11-09, 32:56): Merge policies and Peeksort
- Video 4-7 · transcript (2026-11-09, 21:17): 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). -
Powersort Website with interactive playground and links to deployed Powersort implementations in Java, C++, and Python.
Mergesort with sorted check is indeed also almost optimally adaptive, with $(H+3)n$ mergecost.