Unit 3: Efficient Sorting – The Power of Divide & Conquer

This unit covers

• mergesort and quicksort
• counting sort
• comparions lower bound for sorting
• adaptive sorting
• further divide & conquer algorithms

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

Part I – The Basics

• Video 3-0 · transcript (2023-10-13, 14:39): §3.0 Sorting introduction
  
• Video 3-1 · transcript (2023-10-13, 18:50): §3.1 Mergesort
  
• Video 3-2 · transcript (2023-10-13, 23:11): §3.2 Quicksort
  
• Video 3-3 · transcript (2023-10-13, 15:27): §3.3 Comparison-based lower bound
  
• Video 3-4 · transcript (2023-10-19, 16:04): §3.4 Integer sorting
  

Part II – Exploiting presortedness

• Video 3-5 · transcript (2023-10-19, 34:22): §3.5 Adaptive sorting & Peeksort
  
  Chapters

  3:41 Simple sorting optimizations
  6:44 Analyzing performance metrics
  13:00 Bottom-up merge sort
  17:15 Limitations of current approaches
  22:10 Optimal merging strategies
  27:02 Peak sort and conclusion
  
• Video 3-6 · transcript (2023-10-19, 15:06): §3.6 Python’s list sort & Powersort
  
  Chapters

  2:33 How Timsort functions
  5:50 Limitations of Timsort
  7:10 Introduction to Powersort
  10:20 Balanced tree intuition
  14:19 Conclusion of Powersort
  

Part III – Divide & conquer beyond sorting

• Video 3-7 · transcript (2023-10-20, 32:50): §3.7 Order statistics, quickselect, median of medians
  
  Chapters

  3:31 Selection by rank problem
  8:36 Quick select algorithm
  14:01 Worst-case performance issues
  23:20 Median of medians algorithm
  
• Video 3-8 · transcript (2023-10-20, 15:04): §3.8 Further divide & conquer algorithms
  
  Chapters

  0:28 The majority problem
  2:31 Divide and conquer solution
  7:21 Linear time voting algorithm
  10:41 Closest pair of points
  

---

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

The presentation of quickselect and the median-of-medians algorithm is inspired by material prepared for the module

• Data Structuring and Data Management, University of Waterloo

The other material of Part III is based on

• Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms 3rd ed (2009), MIT Press

---

Unit 2  ⋅  Syllabus  ⋅  Unit 4