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)
References
- 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", https://www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf
- 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", https://jeffe.cs.illinois.edu/teaching/algorithms/notes/12-lowerbounds.pdf (2018)