Comparison Sorting Lower Bounds: Samuel’s tutorial

Summary: Samuel's tutorial on lower bounds on the fastest possible comparison sorting algorithms.
Topics: lower bounds, sorting, algorithms, coding
Slides: link (pdf)

  • H. Steinhaus, "Mathematical Snapshots" (1939)
  • L. Ford and S. Johnson, "A tournament problem", The American Mathematical Monthly (1959)
  • A. Blum and M. Blum, "Comparison-based Lower Bounds for Sorting",
  • D. E. Knuth, "The art of computer programming, vol. 3: sorting and searching", Chap 5.3 (1998)
  • T. Cormen et al., "Introduction to algorithms", Chap 8, MIT press (2022)
  • J. Erickson, "Lower Bounds", (2018)