Document Open Access Logo

Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs

Authors J. Ian Munro , Sebastian Wild

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2018.63.pdf
  • Filesize: 0.62 MB
  • 16 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Sorting and searching
Keywords
  • adaptive sorting
  • nearly-optimal binary search trees
  • Timsort

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We present two stable mergesort variants, "peeksort" and "powersort", that exploit existing runs and find nearly-optimal merging orders with negligible overhead. Previous methods either require substantial effort for determining the merging order (Takaoka 2009; Barbay & Navarro 2013) or do not have an optimal worst-case guarantee (Peters 2002; Auger, Nicaud & Pivoteau 2015; Buss & Knop 2018) . We demonstrate that our methods are competitive in terms of running time with state-of-the-art implementations of stable sorting methods.

Cite As Get BibTex

J. Ian Munro and Sebastian Wild. Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 63:1-63:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.63

Author Details

J. Ian Munro
  • University of Waterloo, Canada
Sebastian Wild
  • University of Waterloo, Canada

Funding

This work was supported by the Natural Sciences and Engineering Research Council of Canada and the Canada Research Chairs Programme.

Supplementary Materials

References

  1. Nicolas Auger, Vincent Jugé, Cyril Nicaud, and Carine Pivoteau. On the worst-case complexity of TimSort. In Hannah Bast Yossi Azar and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms (ESA 2018), Leibniz International Proceedings in Informatics (LIPIcs), 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2018.4.
  2. Nicolas Auger, Cyril Nicaud, and Carine Pivoteau. Merge strategies: from merge sort to TimSort, 2015. URL: https://hal-upec-upem.archives-ouvertes.fr/hal-01212839.
  3. Jérémy Barbay, Johannes Fischer, and Gonzalo Navarro. LRM-trees: Compressed indices, adaptive sorting, and compressed permutations. Theoretical Computer Science, 459:26-41, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2012.08.010.
  4. Jérémy Barbay and Gonzalo Navarro. Compressed representations of permutations, and applications. In Susanne Albers and Jean-Yves Marion, editors, 26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009), pages 111-122, Freiburg, Germany, 2009. URL: https://hal.inria.fr/inria-00358018.
  5. Jérémy Barbay and Gonzalo Navarro. On compressing permutations and adaptive sorting. Theoretical Computer Science, 513:109-123, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2013.10.019.
  6. Jérémy Barbay, Carlos Ochoa, and Srinivasa Rao Satti. Synergistic solutions on multisets. In Juha Kärkkäinen, Jakub Radoszewski, and Wojciech Rytter, editors, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1-31:14, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.CPM.2017.31.
  7. Paul J. Bayer. Improved Bounds on the Cost of Optimal and Balanced Binary Search Trees. Master’s thesis, Massachusetts Institute of Technology, 1975. Google Scholar
  8. Jon L. Bentley and M. Douglas McIlroy. Engineering a sort function. Software: Practice and Experience, 23(11):1249-1265, 1993. URL: http://dx.doi.org/10.1002/spe.4380231105.
  9. Sam Buss and Alexander Knop. Strategies for stable merge sorting, 2018. URL: http://arxiv.org/abs/1801.04641.
  10. Stijn de Gouw, Frank S. de Boer, Richard Bubel, Reiner Hähnle, Jurriaan Rot, and Dominic Steinhöfel. Verifying OpenJDK’s sort method for generic collections. Journal of Automated Reasoning, aug 2017. URL: http://dx.doi.org/10.1007/s10817-017-9426-4.
  11. Amr Elmasry and Abdelrahman Hammad. Inversion-sensitive sorting algorithms in practice. Journal of Experimental Algorithmics, 13:11:1-11:18, 2009. URL: http://dx.doi.org/10.1145/1412228.1455267.
  12. Vladmir Estivill-Castro and Derick Wood. A survey of adaptive sorting algorithms. ACM Computing Surveys, 24(4):441-476, dec 1992. URL: http://dx.doi.org/10.1145/146370.146381.
  13. Harold N. Gabow, Jon Louis Bentley, and Robert E. Tarjan. Scaling and related techniques for geometry problems. In 16th annual ACM symposium on Theory of computing (STOC 1984), pages 135-143. ACM Press, 1984. URL: http://dx.doi.org/10.1145/800057.808675.
  14. Mordecai J. Golin and Robert Sedgewick. Queue-mergesort. Information Processing Letters, 48(5):253-259, dec 1993. URL: http://dx.doi.org/10.1016/0020-0190(93)90088-q.
  15. Chris Hegarty. Replace "modified mergesort" in java.util.Arrays.sort with timsort, 2009. URL: https://bugs.openjdk.java.net/browse/JDK-6804124.
  16. Yasuichi Horibe. An improved bound for weight-balanced tree. Information and Control, 34(2):148-151, jun 1977. URL: http://dx.doi.org/10.1016/S0019-9958(77)80011-9.
  17. Donald E. Knuth. The Art Of Computer Programming: Searching and Sorting. Addison Wesley, 2nd edition, 1998. Google Scholar
  18. Kurt Mehlhorn. Nearly optimal binary search trees. Acta Informatica, 5(4), 1975. URL: http://dx.doi.org/10.1007/BF00264563.
  19. Kurt Mehlhorn. A best possible bound for the weighted path length of binary search trees. SIAM Journal on Computing, 6(2):235-239, 1977. URL: http://dx.doi.org/10.1137/0206017.
  20. Kurt Mehlhorn. Sorting presorted files. In Theoretical Computer Science 4th GI Conference, pages 199-212. Springer, 1979. URL: http://dx.doi.org/10.1007/3-540-09118-1_22.
  21. Kurt Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching. Springer, 1984. Google Scholar
  22. Ian Munro and Philip M. Spira. Sorting and searching in multisets. SIAM Journal on Computing, 5(1):1-8, 1976. URL: http://dx.doi.org/10.1137/0205001.
  23. S.V. Nagaraj. Optimal binary search trees. Theoretical Computer Science, 188(1-2):1-44, nov 1997. URL: http://dx.doi.org/10.1016/S0304-3975(96)00320-9.
  24. Tim Peters. [Python-Dev] Sorting, 2002. URL: https://mail.python.org/pipermail/python-dev/2002-July/026837.html.
  25. Tim Peters. Timsort, 2002. URL: http://hg.python.org/cpython/file/tip/Objects/listsort.txt.
  26. Robert Sedgewick. Quicksort with equal keys. SIAM Journal on Computing, 6(2):240-267, 1977. Google Scholar
  27. Robert Sedgewick. Algorithms in Java. Addison-Wesley, 2003. Google Scholar
  28. Robert Sedgewick and Jon Bentley. Quicksort is optimal (talk slides), 2002. URL: http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf.
  29. Tadao Takaoka. A new measure of disorder in sorting - entropy. In The Fourth Australasian Theory Symposium (CATS 1998), pages 77-86, 1998. Google Scholar
  30. Tadao Takaoka. Partial solution and entropy. In MFCS 2009, pages 700-711, 2009. URL: http://dx.doi.org/10.1007/978-3-642-03816-7_59.
  31. W.A. Walker and C.C. Gotlieb. A top-down algorithm for constructing nearly optimal lexicographic trees. In Graph Theory and Computing, pages 303-323. Elsevier, 1972. URL: http://dx.doi.org/10.1016/B978-1-4832-3187-7.50023-4.
  32. Lutz M. Wegner. Quicksort for equal keys. IEEE Transactions on Computers, C-34(4):362-367, 1985. URL: http://dx.doi.org/10.1109/TC.1985.5009387.
  33. Sebastian Wild. Accompanying code for running time study, 2018. URL: http://dx.doi.org/10.5281/zenodo.1241162.
  34. Sebastian Wild. Quicksort is optimal for many equal keys. In ANALCO 2018, pages 8-22. SIAM, jan 2018. URL: http://dx.doi.org/10.1137/1.9781611975062.2.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact