A faster and adaptive partition function for Quicksort
Resumo
The standard implementations of the Quicksort partitioning function are due to Hoare and Bentley–McIlroy. We discuss how the best performing algorithm is related to the number of repeated keys on the input and verify this experimentally. We extend our analysis to a third partitioning algorithm, which we call the Double Hoare algorithm. It has a similar behaviour to Bentley–McIlroy in comparison to the Hoare algorithm, but it performs better than the usual performance metrics indicate. Using this information, we modify it into an algorithm that dynamically adapts to the number of repeated keys and beats library implementations of the Hoare and Bentley–McIlroy independent of the key repetition density.Referências
J. Bentley and M. McIlroy. “Engineering a sort function”. In: Software: Practice and Experience 23.11 (1993), pp. 1249–1265. DOI: 10.1002/spe.4380231105.
W. Chen. “Probabilistic analysis of algorithms for the Dutch national flag problem”. In: Theoretical Computer Science 341.1 (2005), pp. 398–410. DOI: 10.1016/j.tcs.2005.03.047.
Victor Campos, Israel Mendes, Rodrigo Nogueira, and Wladimir Tavares. A faster and adaptive partition function for Quicksort. Online repository. 2026. url: [link].
E. Dijkstra. A Discipline of Programming. Prentice Hall, 1976. isbn: 978-0132158718.
C. Hoare. “Quicksort”. In: The computer journal 5.1 (1962), pp. 10–16. DOI: 10.1093/comjnl/5.1.10.
C. McMaster. “An analysis of algorithms for the Dutch National Flag Problem”. In: Commun. ACM 21.10 (1978), pp. 842–846. DOI: 10.1145/359619.359629.
M. Nebel, S. Wild, and C. Martínez. “Analysis of pivot sampling in dual-pivot quicksort: A holistic analysis of Yaroslavskiy’s partitioning scheme”. In: Algorithmica 75 (2016), pp. 632–683. DOI: 10.1007/s00453-015-0041-7.
O. Peters. Pattern-defeating Quicksort. 2021. arXiv: 2106.05123. url: [link].
R. Sedgewick and J. Bentley. “Quicksort is Optimal”. KnuthFest. 2002. url: [link] (visited on 03/01/2026).
R. Sedgewick. “Quicksort with equal keys”. In: SIAM Journal on Computing 6.2 (1977), pp. 240–267. DOI: 10.1137/0206018.
W. Chen. “Probabilistic analysis of algorithms for the Dutch national flag problem”. In: Theoretical Computer Science 341.1 (2005), pp. 398–410. DOI: 10.1016/j.tcs.2005.03.047.
Victor Campos, Israel Mendes, Rodrigo Nogueira, and Wladimir Tavares. A faster and adaptive partition function for Quicksort. Online repository. 2026. url: [link].
E. Dijkstra. A Discipline of Programming. Prentice Hall, 1976. isbn: 978-0132158718.
C. Hoare. “Quicksort”. In: The computer journal 5.1 (1962), pp. 10–16. DOI: 10.1093/comjnl/5.1.10.
C. McMaster. “An analysis of algorithms for the Dutch National Flag Problem”. In: Commun. ACM 21.10 (1978), pp. 842–846. DOI: 10.1145/359619.359629.
M. Nebel, S. Wild, and C. Martínez. “Analysis of pivot sampling in dual-pivot quicksort: A holistic analysis of Yaroslavskiy’s partitioning scheme”. In: Algorithmica 75 (2016), pp. 632–683. DOI: 10.1007/s00453-015-0041-7.
O. Peters. Pattern-defeating Quicksort. 2021. arXiv: 2106.05123. url: [link].
R. Sedgewick and J. Bentley. “Quicksort is Optimal”. KnuthFest. 2002. url: [link] (visited on 03/01/2026).
R. Sedgewick. “Quicksort with equal keys”. In: SIAM Journal on Computing 6.2 (1977), pp. 240–267. DOI: 10.1137/0206018.
Publicado
19/07/2026
Como Citar
CAMPOS, Victor; MENDES, Israel; NOGUEIRA, Rodrigo; TAVARES, Wladimir.
A faster and adaptive partition function for Quicksort. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 11. , 2026, Gramado/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 11-15.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2026.21842.
