2026-08-25T18:47:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27150 2026-08-25T13:18:15Z ddc:004 open_access

Virtual-Memory Powersort Moltmann, Finn Nakajima, Tamio-Vesa Wild, Sebastian adaptive sorting inplace sorting inplace merging library sort virtual memory internal buffering Powersort Timsort We give a more space-efficient implementation of adaptive mergesort: Virtual-Memory Powersort. Using internal buffering techniques, we significantly reduce the memory consumption of the algorithm; specifically, for sorting n objects the required buffer area is reduced from space for n/2 objects to O(√{n log n}) objects. While this space-efficiency can be achieved (indeed reduced to O(1)) conceptually very easily with known inplace merging algorithms, using these as a drop-in replacement for the standard merge algorithm incurs a substantial slow-down. Virtual-Memory Powersort, by contrast, uses the same number of moves and comparisons as previous Powersort implementations up to an additive O(n) term. We report on an empirical running-time study comparing our implementation against other Powersort variants and state-of-the-art stable sorting methods, demonstrating that almost in-place stable sorting can be achieved with negligible overhead in many scenarios. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Finn Moltmann and Tamio-Vesa Nakajima and Sebastian Wild 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.14 urn:nbn:de:0030-drops-271501 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.14 eng https://creativecommons.org/licenses/by/4.0/legalcode