{"id":"2402e32d-ae36-43bb-bb39-d8467dca2e51","arxiv_id":"2605.27147","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"Almost-inplace Powersort via recycled virtual pages reduces buffer space to O(√(n log n)) objects with only additive O(n) extra moves over standard Powersort.","lead":"Virtual-Memory Powersort cuts the extra buffer for adaptive stable mergesort from n/2 objects to O(√(n log n)) while matching ordinary Powersort moves and comparisons up to an additive O(n). This makes fast run-adaptive stable sorting usable when a linear temporary array is too expensive.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates the stack-height bound as the key enabler of the space result and rates correctness risk low. Independent verification of the page accounting and of the move/comparison counts (Figs. 6–7) shows no discrepancy with the claimed M + O(n) bounds. The only minor practical caveat—page-size choice and free-list overhead—is already quantified and does not affect the asymptotic claim. Consequently the ACCEPT verdict stands without adjustment.","tokens_in":18276,"tokens_out":375,"duration_ms":3772,"concrete_test":"Re-run the memory-accounting experiment of Fig. 3 for n = 10^8 (instead of ~10^7) with the same page-size formula; if measured extra space remains Θ(√(n log n)) and does not jump to linear, the balancing argument is confirmed at larger scale.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (buffer reduced to O(√(n log n)) objects while moves/comparisons stay M + O(n)) rests on two solid pieces: (1) the known O(log n) stack-height bound of Powersort (Thm 2.2) that limits live partial pages, and (2) standard free-list page accounting that balances metadata O(n/P) against O(log n) extra pages of size P ≈ √(n/(T log^{2} n)). Both are correctly applied in §4; the additive-move bound follows from the page-by-page merge plus a final linear permutation. Experiments and public code corroborate the asymptotic statements. No hidden assumption or gap undermines the claim.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","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.","tokens_in":18457,"tokens_out":692,"duration_ms":6873,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"A few typographical slips remain (e.g., “comparsions”, “auxilliary”, “envel⌢pe” in the author list). A final proof-reading pass is recommended.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is already in excellent shape; the empty major-comment list is intentional. The public code repository and the clean reliance on previously published Powersort theorems make the paper unusually easy to verify. I see no novelty or citation concerns."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The punchline is simple: they take the folklore virtual-page / block-table merge idea, marry it cleanly to Powersort’s O(log n) stack discipline, and get a stable adaptive sort whose extra space drops from n/2 objects to O(√(n log n)) while moves and comparisons stay M + O(n). That is exactly the gap between “in-place merges exist but are slow” and “linear buffers are what people actually ship.”\n\nWhat is new is the combination and the accounting. Powersort’s known stack-height bound (Thm 2.2) limits live partial pages to O(log n); they balance page size against metadata and free-list pages to hit the square-root bound, then keep the inner merge loop essentially identical to a standard merge via unrolling. The Pingpong layout that avoids most extraneous copies is a nice extra. Analysis is short and correct; it rests on prior Powersort results plus ordinary page accounting. Experiments cover four data types (cheap/expensive compare × cheap/expensive move), six run-length regimes, and the right baselines (CPython-style Powersort, std::stable_sort, Wikisort, library in-place merge). Code is public. For large objects the virtual-memory version can even beat the linear-buffer version because it touches less address space.\n\nSoft spots are minor and proportional. Page size is a free parameter (they choose a power of two near the asymptotic optimum); minimum-run insertion-sort length is the usual Timsort rule. No error bars, single machine, no galloping. None of that undermines the central claim. Fully in-place black-box merge is shown to be uncompetitive, which is honest and useful.\n\nThis is for people who write or maintain library sorts, or who care about adaptive stable sorting under memory pressure. Theory people will find the asymptotics unsurprising; practitioners will find the numbers and the code immediately usable. The math, data, and citations look solid. I would send it to referees without hesitation and would cite the space/move trade-off and the Pingpong observation myself.","headline":"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.","tokens_in":19044,"tokens_out":534,"would_cite":true,"duration_ms":9130,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"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.","keywords":["adaptive sorting","inplace sorting","inplace merging","library sort","virtual memory","internal buffering","Powersort","Timsort"],"falsifier":"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.","tokens_in":19206,"feed_emoji":"💾","tokens_out":654,"duration_ms":5495,"temperature":0.7,"pith_summary":"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.","feed_headline":"Adaptive mergesort buffer drops from n/2 to √n log n","feed_subtitle":"Virtual pages keep move and comparison counts essentially unchanged, so almost in-place stable sorting costs little.","key_machinery":"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)).","core_discovery":"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.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Powersort buffer cut from n/2 to O(√(n log n))","Almost in-place Powersort uses O(√(n log n)) buffer","Virtual-Memory Powersort: same moves, far less space","Adaptive mergesort now needs only √(n log n) buffer","Near in-place stable Powersort without merge slowdown"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Powersort buffer cut from n/2 to O(√(n log n))","Almost in-place Powersort uses O(√(n log n)) buffer","Virtual-Memory Powersort: same moves, far less space","Adaptive mergesort now needs only √(n log n) buffer","Near in-place stable Powersort without merge slowdown"]},"model":"grok-4.5","effort":"low","cost_usd":0.003918,"raw_usage":{"total_tokens":1187,"prompt_tokens":705,"num_sources_used":0,"completion_tokens":96,"cost_in_usd_ticks":39180000,"prompt_tokens_details":{"text_tokens":705,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":386,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":705,"tokens_out":96,"duration_ms":3459,"temperature":1.0,"reasoning_tokens":386,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-12T15:54:18.071269+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":2}