Bibliography

Astrelin, Andrey. 2013. “Grailsort.” https://github.com/Mrrl/GrailSort.

———. 2014. “SqrtSort.” https://github.com/Mrrl/SqrtSort.

Aumüller, Martin, and Martin Dietzfelbinger. 2015. “Optimal Partitioning for Dual-Pivot Quicksort.” ACM Trans. Algorithms 12 (2). https://doi.org/10.1145/2743020.

Aumüller, Martin, Martin Dietzfelbinger, and Pascal Klaue. 2016. “How Good Is Multi-Pivot Quicksort?” ACM Trans. Algorithms 13 (1). https://doi.org/10.1145/2963102.

Axtmann, Michael, Sascha Witt, Daniel Ferizovic, and Peter Sanders. 2017. “In-Place Parallel Super Scalar Samplesort (IPSSSSo).” In 25th Annual European Symposium on Algorithms (ESA 2017), edited by Kirk Pruhs and Christian Sohler, 87:9:1–14. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.ESA.2017.9.

Bender, Michael A., Martin Farach-Colton, and Miguel A. Mosteiro. 2006. “Insertion Sort Is o(n Log n).” Theory of Computing Systems 39 (3): 391–97.

Bentley, Jon L., and M. Douglas McIlroy. 1993. “Engineering a Sort Function.” Softw. Pract. Exper. 23 (11): 1249–65.

Blum, Manuel, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan. 1973. “Time Bounds for Selection.” J. Comput. Syst. Sci. 7 (4): 448–61.

Brodal, Gerth Stølting, Rolf Fagerberg, and Kristoffer Vinther. 2008. “Engineering a Cache-Oblivious Sorting Algorithm.” ACM Journal of Experimental Algorithmics 12 (December).

Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition. 3rd ed. The MIT Press.

Edelkamp, Stefan, and Armin Weiss. 2016. “BlockQuicksort: Avoiding Branch Mispredictions in Quicksort.” In 24th Annual European Symposium on Algorithms (ESA 2016), edited by Piotr Sankowski and Christos Zaroliagis, 57:38:1–16. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.ESA.2016.38.

Edelkamp, Stefan, and Armin Weiß. 2016. “BlockQuicksort: How Branch Mispredictions Don’t Affect Quicksort.” CoRR abs/1604.06697. https://arxiv.org/abs/1604.06697.

Frigo, Matteo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran. 1999. “Cache-Oblivious Algorithms.” In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 285–85. FOCS ’99. Washington, DC, USA: IEEE Computer Society.

Hoare, C. A. R. 1961a. “Algorithm 63: Partition.” Commun. ACM 4 (7): 321.

———. 1961b. “Algorithm 64: Quicksort.” Commun. ACM 4 (7): 321.

———. 1961c. “Algorithm 65: Find.” Commun. ACM 4 (7): 321–22.

———. 1962. “Quicksort.” The Computer Journal 5 (1): 10–16. https://doi.org/10.1093/comjnl/5.1.10.

Huang, B.-C., and M. A. Langston. 1992. “Fast Stable Merging and Sorting in Constant Extra Space.” J-COMP-J 35 (6): 643–50.

Kamp, Poul-Henning. 2011. “The Most Expensive One-Byte Mistake.” Commun. ACM 54 (9): 42–44.

Katajainen, Jyrki, and Jesper Larsson Träff. 1997. “A Meticulous Analysis of Mergesort Programs.” In Algorithms and Complexity, edited by Giancarlo Bongiovanni, Daniel Pierre Bovet, and Giuseppe Di Battista, 217–28. Berlin, Heidelberg: Springer Berlin Heidelberg.

Knuth, Donald. 1973. The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley.

Knuth, Donald E. 1998. The Art of Computer Programming, Volume 3: (2nd Ed.) Sorting and Searching. Redwood City, CA, USA: Addison Wesley Longman Publishing Co., Inc.

Kuhn, Thomas S. 1962. The Structure of Scientific Revolutions. Chicago: University of Chicago Press.

Liu, Yuhang, Xian-He Sun, Yang Wang, and Yungang Bao. 2021. “HCDA: From Computational Thinking to a Generalized Thinking Paradigm.” Commun. ACM 64 (5): 66–75. https://doi.org/10.1145/3418291.

Martínez, Conrado, Markus E. Nebel, and Sebastian Wild. 2015. “Analysis of Branch Misses in Quicksort.” In Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2015, San Diego, CA, USA, January 4, 2015, edited by Robert Sedgewick and Mark Daniel Ward, 114–28. SIAM. https://doi.org/10.1137/1.9781611973761.11.

Martínez, Conrado, Markus Nebel, and Sebastian Wild. 2019. “Sesquickselect: One and a Half Pivots for Cache-Efficient Selection.” In Proceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2019, San Diego, CA, USA, January 6, 2019, edited by Marni Mishna and J. Ian Munro, 54–66. SIAM. https://doi.org/10.1137/1.9781611975505.6.

Munro, J. Ian, and Sebastian Wild. 2018. “Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs.” In 26th Annual European Symposium on Algorithms (ESA 2018), edited by Yossi Azar, Hannah Bast, and Grzegorz Herman, 112:63:1–16. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.ESA.2018.63.

Musser, David R. 1997. “Introspective Sorting and Selection Algorithms.” Softw. Pract. Exper. 27 (8): 983–93.

Navarro, Gonzalo, and Rodrigo Paredes. 2010. “On Sorting, Heaps, and Minimum Spanning Trees.” Algorithmica 57 (4): 585–620.

Nebel, Markus E., Sebastian Wild, and Conrado Martínez. 2016. “Analysis of Pivot Sampling in Dual-Pivot Quicksort: A Holistic Analysis of Yaroslavskiy’s Partitioning Scheme.” Algorithmica 75 (4): 632–83. https://doi.org/10.1007/s00453-015-0041-7.

O’Neil, Patrick, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil. 1996. “The Log-Structured Merge-Tree (LSM-Tree).” Acta Inf. 33 (4): 351–85. https://doi.org/10.1007/s002360050048.

Oehlschlägel, Jens, and Leonardo Silvestri. 2012. Bit64: A S3 Class for Vectors of 64bit Integers. https://CRAN.R-project.org/package=bit64.

Peters, Orson. 2014. “[PATCH] Bug 20837 - Libc++ Std::sort Has o(n²) Worst Case, Standard Mandates o(n Log(n)).” llvm bug report. https://bugs.llvm.org/show_bug.cgi?id=20837.

———. 2015. “Pdqsort.” github code. https://github.com/orlp/pdqsort.

Peters, Orson R. L. 2021a. “Agreed on Pdqsort ...” Hacker News. https://news.ycombinator.com/item?id=27795484.

———. 2021b. “Pattern-Defeating Quicksort.” CoRR abs/2106.05123. https://arxiv.org/abs/2106.05123.

———. 2023a. “Glidesort.” Github. https://github.com/orlp/glidesort.

———. 2023b. “Glidesort, Efficient in-Memory Adaptive Stable Sorting on Modern Hardware.” Talk given at FOSSDEM23. https://fosdem.org/2023/schedule/event/rust_glidesort.

Peters, Tim. 2002. “I Wrote a Sort for Python.” ’Sorting’ mail to the Python-Dev list. https://mail.python.org/pipermail/python-dev/2002-July/026837.html.

Sandlund, Bryce, and Sebastian Wild. 2020. “Lazy Search Trees.” In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), 704–15.

Sedgewick, Robert. 1975. Quicksort. Outstanding Dissertations in the Computer Sciences. Garland Publishing, New York.

———. 1977a. “Quicksort with Equal Keys.” SIAM J. Comput, 240–67.

———. 1977b. “The Analysis of Quicksort Programs.” Acta Inf. 7: 327–55.

———. 1978. “Implementing Quicksort Programs.” Commun. ACM 21 (10): 847–57.

———. 1990. Algorithms in c. 2nd ed. Addison-Wesley Professional.

———. 1998. Algorithms in c, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching, Third Edition. 3rd ed. Addison-Wesley Professional.

Sedgewick, Robert, and Jon Bentley. 2002. “Quicksort Is Optimal.” Stanford University.

Singleton, Richard C. 1969. “Algorithm 347: An Efficient Algorithm for Sorting with Minimal Storage [M1].” Commun. ACM 12 (3): 185–86. https://doi.org/10.1145/362875.362901.

Steffen, Dagmar. 2010. “Design Semantics of Innovation.” Design Semiotics in Use, 82–110.

Wild, Sebastian. 2012. “Java 7’s Dual Pivot Quicksort.” Master’s thesis, University of Kaiserslautern.

———. 2016. “Dual-Pivot Quicksort and Beyond: Analysis of Multiway Partitioning and Its Practical Potential.” Doctoralthesis, Technische Universität Kaiserslautern. https://nbn-resolving.de/urn:nbn:de:hbz:386-kluedo-44682.

———. 2017. “Quicksort Mit Zwei Pivots Und Mehr: Eine Mathematische Analyse von Mehrwege-Partitionierungsverfahren Und Der Frage, Wie Quicksort Dadurch Schneller Wird.” In Ausgezeichnete Informatikdissertationen 2016, edited by Steffen Hölldobler, 319–28. Bonn: Gesellschaft für Informatik e.V.

———. 2018a. “Dual-Pivot and Beyond: The Potential of Multiway Partitioning in Quicksort.” It - Information Technology 60 (3): 173–77. https://doi.org/10.1515/itit-2018-0012.

———. 2018b. “Quicksort Is Optimal for Many Equal Keys.” In Proceedings of the Fifteenth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2018, New Orleans, LA, USA, January 8-9, 2018, edited by Markus E. Nebel and Stephan G. Wagner, 8–22. SIAM. https://doi.org/10.1137/1.9781611975062.2.

Wild, Sebastian, and Markus E. Nebel. 2012. “Average Case Analysis of Java 7’s Dual Pivot Quicksort.” In European Symposium on Algorithms 2012 (LNCS), 7501:825–36.

Wild, Sebastian, Markus E. Nebel, and Hosam M. Mahmoud. 2016. “Analysis of Quickselect Under Yaroslavskiy’s Dual-Pivoting Algorithm.” Algorithmica 74 (1): 485–506. https://doi.org/10.1007/s00453-014-9953-x.

Wild, Sebastian, Markus E. Nebel, and Ralph Neininger. 2015. “Average Case and Distributional Analysis of Dual-Pivot Quicksort.” ACM Trans. Algorithms 11 (3): 22:1–42.

Wild, Sebastian, Markus E. Nebel, Raphael Reitzig, and Ulrich Laube. 2013. “Engineering Java 7’s Dual Pivot Quicksort Using MaLiJan.” In ALENEX.

Williams, J. W. J. 1964. “Algorithm 232: Heapsort.” Communications of the ACM 7 (6): 347–48.

Yaroslavskiy, Vladimir. 2009. “Dual-Pivot Quicksort.” https://iaroslavski.narod.ru/quicksort/.