2026-07-20T06:35:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9526 2024-03-06T10:43:58Z ddc:004 open_access

Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs Munro, J. Ian Wild, Sebastian adaptive sorting nearly-optimal binary search trees Timsort 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik J. Ian Munro and Sebastian Wild 2018 Is Part Of LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2018.63 urn:nbn:de:0030-drops-95265 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.63 eng https://creativecommons.org/licenses/by/3.0/legalcode