DROPS

Artifact

Software

Virtual Memory Powersort

Authors: Finn Moltmann, Tamio-Vesa Nakajima, and Sebastian Wild

Abstract

Cite as

Finn Moltmann, Tamio-Vesa Nakajima, Sebastian Wild. Virtual Memory Powersort (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-27635,
   title = {{Virtual Memory Powersort}}, 
   author = {Moltmann, Finn and Nakajima, Tamio-Vesa and Wild, Sebastian},
   note = {Software, version 1.0., Sebastian Wild: EPSRC grant EP/X039447/2, swhId: \href{https://archive.softwareheritage.org/swh:1:snp:8e65d4e51fc7e84ac78dde26a19bea76773d8ce8;origin=https://git.sr.ht/~tamionv/vm-powersort}{\texttt{swh:1:snp:8e65d4e51fc7e84ac78dde26a19bea76773d8ce8}} (visited on 2026-08-25)},
   url = {https://git.sr.ht/~tamionv/vm-powersort},
   doi = {10.4230/artifacts.27635},
}

Document

DOI: 10.4230/LIPIcs.ESA.2026.14

Virtual-Memory Powersort

Authors: Finn Moltmann, Tamio-Vesa Nakajima, and Sebastian Wild

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

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.

Cite as

Finn Moltmann, Tamio-Vesa Nakajima, and Sebastian Wild. Virtual-Memory Powersort. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{moltmann_et_al:LIPIcs.ESA.2026.14,
  author =	{Moltmann, Finn and Nakajima, Tamio-Vesa and Wild, Sebastian},
  title =	{{Virtual-Memory Powersort}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{14:1--14:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.14},
  URN =		{urn:nbn:de:0030-drops-271501},
  doi =		{10.4230/LIPIcs.ESA.2026.14},
  annote =	{Keywords: adaptive sorting, inplace sorting, inplace merging, library sort, virtual memory, internal buffering, Powersort, Timsort}
}

Search Results

Documents authored by Moltmann, Finn

Virtual Memory Powersort

Abstract

Cite as

Virtual-Memory Powersort

Abstract

Cite as

Thanks for your feedback!

Could not send message