Unit 4: Efficient Sorting

This unit covers

• mergesort and quicksort
• counting sort
• comparions lower bound for sorting
• adaptive sorting

Learning outcomes

1. Know principles and implementation of mergesort and quicksort.
2. Know properties and performance characteristics of mergesort and quicksort.
3. Know the comparison model and understand the corresponding lower bound.
4. Understand counting sort and how it circumvents the comparison lower bound.
5. Know ways how to exploit presorted inputs.

Material

• slides

• lecture notes

• Mergesort

• Linear Term of Mergesort

• Quicksort

• Quicksort & BSTs

• Sorting Algorithm Decision Trees

• Mergesort with sorted check
• Peeksort
• Powersort

• Analysis of 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 (2026-11-03): Quicksort
  
• Video 4-3 (2026-11-03): Comparison-Based Lower Bound
  
• Video 4-3 (2026-11-03): Integer Sorting
  
• Video 4-4 (2026-11-03): Mergesort with sorted check
  

---

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).

Mergesort with sorted check is indeed also almost optimally adaptive, with $(H+3)n$ mergecost.

---

Unit 3  ⋅  Syllabus  ⋅  Unit 5