Pith. sign in

REVIEW 4 minor 12 references

Virtual-Memory Powersort cuts the buffer for adaptive stable mergesort from n/2 objects to O(√(n log n)) while keeping move and comparison counts essentially the same.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-12 15:54 UTC pith:KVKHVHUK

load-bearing objection Practical almost-in-place Powersort that keeps move/comparison counts near-optimal and ships working code; a real library-level advance, not a theory paper.

arxiv 2605.27147 v2 pith:KVKHVHUK submitted 2026-05-26 cs.DS cs.PF

Virtual-Memory Powersort

Finn Moltmann , Tamio-Vesa Nakajima , Sebastian Wild This is my paper
classification cs.DS cs.PF
keywords adaptive sortinginplace sortinginplace merginglibrary sortvirtual memoryinternal bufferingPowersortTimsort
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Standard adaptive mergesorts such as Powersort need a linear buffer of size n/2 so that they can merge runs quickly and stably. Fully in-place merges exist, but they slow the whole algorithm down. This paper shows how to keep almost the same move and comparison counts while shrinking the buffer to O(√(n log n)) objects. The method treats the input as pages, lets intermediate runs live as linked sequences of pages that need not be contiguous, and reclaims each exhausted page for later output. Because Powersort itself keeps only O(log n) runs on its stack, the number of partially filled pages stays small, so the extra space stays quadratic-root after the page size is balanced. Empirical timings on integers and large records show that the overhead is often negligible and can even reverse for large objects.

Core claim

Virtual-Memory Powersort realises Powersort with only O(√(n log n)) extra memory while performing the same number of element moves and comparisons as ordinary Powersort implementations up to an additive O(n) term, thereby delivering almost in-place stable adaptive sorting without the slowdown of known fully in-place merges.

What carries the argument

Virtual runs: each run is stored as a sequence of fixed-size pages that may sit at arbitrary physical addresses; exhausted input pages are immediately returned to a free list and reused as output pages. Powersort's O(log n) stack-height bound keeps the number of partially filled pages logarithmic, allowing the page size to be chosen so that total extra space is O(√(n log n)).

Load-bearing premise

The argument needs Powersort's guarantee that only O(log n) runs ever sit on the stack at once; any merge policy that kept more simultaneous runs would inflate the number of partial pages and break the space bound.

What would settle it

Measure the number of live partial pages (or peak extra memory) while sorting inputs whose natural-run structure forces a merge policy to keep ω(log n) runs simultaneously; if that quantity grows faster than O(√(n log n)), the space claim fails for that policy.

Watch this falsifier — get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper presents Virtual-Memory Powersort, a space-efficient adaptive mergesort that reduces the auxiliary buffer from n/2 objects to O(√(n log n)) objects while preserving the comparison and move counts of standard Powersort up to an additive O(n) term. It realises this by managing memory in pages of size P ≈ √(n/(T log^{2} n)), representing runs as (possibly non-contiguous) sequences of pages linked by successor pointers, and recycling exhausted input pages into a free list for output. The analysis relies on Powersort’s known O(log n) stack-height bound (Theorem 2.2) to limit the number of live partial pages, together with standard free-list accounting. A secondary “Pingpong Powersort” variant that uses a full linear buffer but only M+n moves is also introduced. Extensive C++ experiments on four data types, six run-length regimes and strong baselines (CPython-style Powersort, std::stable_sort, Wikisort, library in-place merge) support the claim of negligible overhead in many practical scenarios.

Significance. The result fills a genuine practical gap: library-stable adaptive sorts currently demand a linear buffer, while fully in-place stable merges are too slow for production use. By exploiting Powersort’s stack discipline the authors obtain a clean O(√(n log n))-space algorithm whose inner loop is essentially identical to ordinary merging (via page-wise unrolling). The accompanying public implementation, the Pingpong variant that minimises moves, and the careful experimental design (four cost regimes, 100 iterations) make the contribution immediately usable and reproducible. The work is therefore of clear interest both to algorithm engineers and to library maintainers.

minor comments (4)
  1. In §4 the page-size formula is written P ≈ √(n/(T log^{2} n)); a short explicit derivation balancing the O(n/P) metadata term against the O(log n)·P·T extra-page term would make the constant factors transparent.
  2. Figure 3 reports only average memory; adding the observed maximum (or a short table of peak usage) would strengthen the space claim for the worst-case O(√(n log n)) bound.
  3. The discussion of galloping merges (end of §2.1) is intriguing but left as future work; a one-sentence remark on whether page-boundary checks would destroy the galloping advantage would be helpful.
  4. A few typographical slips remain (e.g., “comparsions”, “auxilliary”, “envel⌢pe” in the author list). A final proof-reading pass is recommended.

Circularity Check

1 steps flagged

No significant circularity; space and move bounds follow from standard page accounting plus the independently published O(log n) stack-height property of Powersort.

specific steps
  1. self citation load bearing [§2, Theorem 2.2 (citing [1, Thm 3.3, Rem 3.4]) and its use in §4 “Pages needed”]
    "▶ Theorem 2.2([ 1, Thm 3.3, Rem 3.4]). … 1.The stack has height bounded by⌈log2n⌉+ 1. … Hence overall we need n/P + O(log 2(n)) pages."

    The O(log n) live-run bound is essential to keep the extra-page term O(log n) after balancing page size; without it the claimed O(√(n log n)) space would not hold. The bound is imported from prior work co-authored by one of the present authors. The citation is nevertheless a genuine theorem (not a uniqueness claim or fitted ansatz) and does not force the space or move counts by construction.

full rationale

The central claims (buffer reduced to O(√(n log n)) objects while moves/comparisons remain M+O(n)) are derived in §4 by elementary free-list accounting: at most ⌈n/P⌉ full pages plus O(log n) partial pages (from the stack) and O(n/P) metadata words, balanced by choosing P≈√(n/(T log^{2} n)). The only external ingredient is the stack-height bound of Theorem 2.2, taken from the prior Powersort literature. That bound is a proven combinatorial fact about the merge policy, not a fitted parameter, uniqueness claim, or ansatz; it is externally falsifiable by inspecting any Powersort run stack. No quantity is defined in terms of the quantity being “predicted,” no free parameters are fitted to data and then re-presented as predictions, and the empirical section simply measures the implemented algorithms. The minor author overlap with the cited Powersort papers does not create a circular reduction. Score 1 reflects only the presence of that self-citation; the derivation itself is self-contained.

Axiom & Free-Parameter Ledger

2 free parameters · 3 axioms · 0 invented entities

The central space claim rests on two external theorems about Powersort plus a standard page-size balancing argument; the only free design choice is the concrete page size (and the Timsort-style minimum run length). No new physical entities are postulated.

free parameters (2)
  • page size P = ≈ √(n/(T log² n))
    Chosen ≈ √(n/(T log² n)) (and a power of two) to balance metadata words against extra pages; the asymptotic O(√(n log n)) result is insensitive to constant factors but the practical constant is set by hand.
  • minimum run length = Timsort rule
    Taken from Timsort’s classic rule (start from n, repeatedly ceil-divide by 2 until < 64); affects only the constant-factor overhead of insertion-sort run formation.
axioms (3)
  • domain assumption Powersort stack height ≤ ⌈log₂ n⌉ + 1 and merge cost ≤ n(H + 2) (Theorem 2.2, citing Munro–Wild / Cawley Gelling et al.)
    Used throughout §4 to bound the number of simultaneous partial pages and therefore the extra space.
  • standard math Standard word-RAM / comparison model; element moves and comparisons are the cost measures
    Implicit throughout the complexity claims.
  • domain assumption A page that has been completely consumed may be recycled as a free output page without further data movement
    Core of the virtual-memory technique (§4, Figure 2).

pith-pipeline@v1.1.0-grok45 · 22424 in / 2287 out tokens · 32552 ms · 2026-07-12T15:54:18.071269+00:00 · methodology

0 comments
read the original 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(\sqrt{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.

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 9 canonical work pages

  1. [1]

    Cawley Gelling, M

    1 W. Cawley Gelling, M. E. Nebel, B. Smith, and S. Wild. Multiway powersort. InSymposium on Algorithm Engineering and Experiments (ALENEX), pages 190–200, 2023.doi:10.1137/1. 9781611977561.ch16. 2 B. Chandramouli and J. Goldstein. Patience is a virtue: revisiting merge and sort on modern processors. InSIGMOD International Conference on Management of Data,...

    doi:10.1137/1 2023

  2. [2]

    Edelkamp, A

    5 S. Edelkamp, A. Weiß, and S. Wild. QuickXsort – a fast sorting scheme in theory and practice. Algorithmica, 82(3):509–588, 2020.doi:10.1007/s00453-019-00634-0. 6 A. Elmasry and A. Hammad. Inversion-sensitive sorting algorithms in practice.ACM Journal of Experimental Algorithmics, 13, Feb. 2009.doi:10.1145/1412228.1455267. 7 V. Estivill-Castro and D. Woo...

    work page doi:10.1007/s00453-019-00634-0 2020

  3. [3]

    Schloss Dagstuhl – Leibniz-Zentrum für Informatik.doi:10.4230/LIPIcs.ICALP.2022

    work page doi:10.4230/lipics.icalp.2022 2022

  4. [4]

    Ghasemi, V

    11 E. Ghasemi, V. Jugé, G. Khalighinejad, and H. Yazdanyar. Galloping in fast-growth natural merge sorts.Algorithmica, 87(2):242–291, Dec. 2024.doi:10.1007/s00453-024-01285-6. 12 G. Graefe. Implementing sorting in database systems.ACM Computing Surveys, 38(3):10, 2006.doi:10.1145/1132960.1132964. 13 B.-C. Huang and M. A. Langston. Practical in-place mergi...

    work page doi:10.1007/s00453-024-01285-6 2024

  5. [5]

    doi:10.1007/978-3-540-30140-0_63. 17 P.-S. Kim and A. Kutzner. Ratio based stable in-place merging. InTheory and Applications of Models of Computation (TAMC), TAMC’08, page 246–257, Berlin, Heidelberg,

    work page doi:10.1007/978-3-540-30140-0_63

  6. [6]

    Mannila and E

    19 H. Mannila and E. Ukkonen. A simple linear-time algorithm for in situ merging.Information Processing Letters, 18(4):203–208, May 1984.doi:10.1016/0020-0190(84)90112-1. 20 M. McFadden (BonzaiThePenguin). WikiSort,

    work page doi:10.1016/0020-0190(84)90112-1 1984

  7. [7]

    URL: https://github.com/bonzaithepenguin/ wikisort. 21 P. McIlroy. Optimistic sorting and information theoretic complexity. InSODA 1993, pages 467–474. SIAM, Jan

    1993

  8. [8]

    URL:http://dl.acm.org/citation.cfm?id=313559.313859. 22 K. Mehlhorn. A best possible bound for the weighted path length of binary search trees.SIAM Journal on Computing, 6(2):235–239, June 1977.doi:10.1137/0206017. 23K. Mehlhorn.Data Structures and Algorithms 1: Sorting and Searching. Springer,

    work page doi:10.1137/0206017 1977

  9. [9]

    doi:10.4230/LIPIcs.ESA.2018.63. 25 L. T. Pardo. Stable Sorting and Merging with Optimal Space and Time Bounds.SIAM Journal on Computing, 6(2):351–372, June 1977.doi:10.1137/0206025. 26 T. Peters. Timsort (listsort.txt),

    work page doi:10.4230/lipics.esa.2018.63 2018

  10. [10]

    URL: https://github.com/python/cpython/blob/ 3ddb856ed1fcfbfb750b00a60b9a5df76555751e/Objects/listsort.txt. 27 O. Petersson and A. Moffat. A framework for adaptive sorting. InScandinavian Workshop on Algorithm Theory (SWAT), page 422–433. Springer, 1992.doi:10.1007/3-540-55706-7_38. 28 O. Petersson and A. Moffat. A framework for adaptive sorting.Discrete ...

    work page doi:10.1007/3-540-55706-7_38 1992

  11. [11]

    URL:https://urn.fi/URN:NBN:fi-fe201402051375. 31 S. Wild. Average cost of QuickXsort with pivot sampling. InInternational Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA), volume 110 ofLIPIcs, pages 36:1–36:19. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018.doi:10.4230/LIPIcs.AofA.2018.36. 32 ...

    work page doi:10.4230/lipics.aofa.2018.36 2018

  12. [12]

    /usr/include/x86_64−linux−gnu/c++/10

    18 Virtual-Memory Powersort A Further optimisations Pre-allocation of buffers.To reduce the cost of allocating and deallocating memory, as well as to improve memory locality, it is advantageous to allocate all the extra memory used by the algorithm once, at the beginning of the run. Simply allocate enough space for all the memory we could need in the wors...

    arXiv