Pith. sign in

REVIEW 5 minor 29 references

Top-Down Mergesort with Sorted Check Has Mergecost $\le(\mathcal H+3)n$

T0 review · 0 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read Standard top-down mergesort with a single sorted check before each merge has mergecost at most $(H+3)n$ for any input, where $H$ is run-length entropy.

desk verdict Correct folklore bound for Mergesort with sorted check, but Equation (1) is an inequality, not an equality. read the letter →

arxiv 2608.08348 v1 pith:HUIGC6PQ submitted 2026-08-08 cs.DS

Sebastian Wild This is my paper · ORCID
classification cs.DS MSC 68W4068P10
keywords mergesortrun-adaptivesortingmergecostrun-lengthentropysortedchecktop-downrecursionboundsadaptiveanalysis
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves that a tiny modification to textbook top-down mergesort—one extra comparison to test whether the two sorted halves are already in order before merging—gives the algorithm a provable run-adaptive guarantee. For any input consisting of $r$ runs of lengths $L_1,\ldots,L_r$, the total merge cost $M$ (the sum of output sizes of all merge steps actually performed) is at most $(H+3)n$, where $H = \sum_i (L_i/n)\log_2(n/L_i)$ is the run-length entropy. The entropy term is the information-theoretic lower bound for any comparison-based sorter, so this shows the simple check comes within a small additive constant of optimal adaptivity without ever explicitly detecting runs. The result matters because it quantifies what a one-line optimization buys in practice: a standard library sorting routine can become run-adaptive essentially for free.

What carries the argument

The load-bearing mechanism is the per-run charging scheme. Equation (1) rewrites the mergecost $M$ as $\sum_i M(R_i)$, where each run $R$ pays $\lvert v \cap R\rvert$ for every recursion-tree node $v$ whose interval properly intersects $R$ or contains it. At any depth $d$ of the recursion tree, the node intervals partition the array, so a contiguous run can be charged by at most two nodes; each such node has size at most $\lceil n/2^d\rceil$. Charging the run $\min\{L, 2\lceil n/2^d\rceil\}$ per level and summing gives $M(R) \le L(\log_2(n/L)+3)$, where the constant 3 emerges from an inequality involving the fractional part of $\log_2(2n/L)$. The Double Ceiling Lemma and the Node Sizes Lemma extend the argument from powers of two to arbitrary $n$.

What would settle it

For a fixed $n$ and run length $L$, enumerate all placements of a run of length $L$ in the recursion tree and compute the exact per-run cost $M(R)$; the theorem predicts $M(R) \le L(\log_2(n/L)+3)$ for every placement. A single placement violating this inequality, or any input with $M > (H+3)n$, would falsify the central claim.

Watch

Extended reading notes

Core claim

The central claim is that top-down recursive Mergesort with the sorted check has mergecost $M \le (H+3)n$ for every input, where $H$ is the run-length entropy. The proof decomposes $M$ into per-run contributions $M(R_i)$ via a charging scheme: each run pays for its share of every merge it participates in. It then shows a single run of length $L$ contributes at most $L(\log_2(n/L)+3)$, so summing over runs yields the entropy bound. For powers of two the argument is a level-by-level calculation; for general $n$, two small lemmas—a double-ceiling identity $\lceil\lceil n/p\rceil/q\rceil = \lceil n/(pq)\rceil$ and a node-size bound $\lvert v\rvert \le \lceil n/2^d\rceil$—extend the same calculation. The paper also notes the bound is asymptotically tight: on inputs with run lengths $1, n-2, 1$, the mergecost is $3n - O(1)$ while $H$ is tiny, so the $+3n$ term cannot be improved by more than a lower-order term in general.

Load-bearing premise

The proof assumes that at any one recursion depth, a contiguous run can be split across at most two subproblems; if a run could touch three or more subproblems at the same depth, the per-level charge of $2n/2^d$ would be too low and the bound could fail.

Editorial extensions

If this is right

  • A comparison-based sorter that never scans for runs can still be run-adaptive: the sorted-check mergesort matches the $(H+2)n$ guarantee of run-detecting mergesorts up to one extra $n$ in the worst case.
  • The bound holds for all inputs; sorted, reverse-sorted, and random inputs all satisfy $M \le (H+3)n$, with random inputs having $H \approx \log_2 n$ and mergecost near $n\log_2 n$.
  • The constant 3 is asymptotically tight: inputs with three runs of lengths $1$, $n-2$, and $1$ force mergecost $3n - O(1)$, so the bound cannot be strengthened by more than a lower-order term in general.
  • The proof's level-by-level accounting works for any $n$, not just powers of two, thanks to the Double Ceiling Lemma and the Node Sizes Lemma.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same two-nodes-per-level charging argument should carry over to bottom-up mergesort, whose passes also partition the array into disjoint intervals; an analogous $(H+3)n$ bound for iterative mergesort would follow with essentially the same proof.
  • Because the sorted check costs only one comparison per merge, the overhead on random data is negligible, while on nearly sorted data the algorithm should mimic run-adaptive sorters; this makes the variant an attractive drop-in for library sorts that avoid explicit run detection.
  • The proof's intermediate inequality replaces the constant 3 by $2 - \theta + 2^\theta$ with $\theta \in [0,1)$, so an input-dependent refinement of the bound is available; one could state the per-run guarantee with this sharper constant and tighten the additive term for specific run-length ratios.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 5 minor

Summary. The paper analyzes top-down recursive Mergesort augmented with a single sorted-check comparison before each merge, and claims that for any input of length n consisting of r runs of lengths L_1,...,L_r, the total mergecost M (sum of output sizes of all merge calls actually performed) satisfies M ≤ (H+3)n, where H = Σ (L_i/n) log2(n/L_i) is the run-length entropy. The proof decomposes the cost per run, establishes a per-run bound of L_i(log2(n/L_i)+3) via level-by-level charging and a geometric-sum calculation for the power-of-two case, and then extends to general n using two elementary rounding lemmas. A short tightness example is also given.

Significance. If correct, this is a clean, parameter-free, self-contained proof of a natural bound for a folklore algorithm. The bound is only slightly weaker than the (H+2)n guarantees of more sophisticated run-adaptive schemes, and it is achieved by the simplest possible modification of textbook Mergesort. The derivation is fully explicit and contains no fitted constants or hidden normalization choices, which is a strength. The main value of the paper is expository: it documents and rigorously proves a result that the authors state was folklore but unpublished, with a short and readable argument.

minor comments (5)
  1. [Section 1, Eq. (1)] Equation (1) is stated as an equality, but it is not an equality for the algorithm with the sorted check: the merge at a node v can be skipped even when R_i ⊆ v or v properly intersects R_i, so the actual mergecost is only bounded above by the right-hand side. For example, on A = [1,3,2] with runs [0,2) and [2,3), the root merge is skipped although both runs are contained in the root, so the right-hand side overcounts the actual cost. The subsequent proof uses only the upper bound, so the theorem survives, but the displayed equation should be changed to 'M ≤ ...' or the text should clarify that M(R_i) is an upper-bound charge rather than the exact contributed cost.
  2. [Section 2, paragraph after Eq. (1)] The statement that 'there can be at most 2 nodes v∈T at depth d that contribute to M(R)' is used to justify the per-level bound, but it is not proved. It is true because the nodes at a fixed depth partition [0,n) and the run R is a contiguous interval, but the proof should state this explicitly as a one-sentence lemma so the reader does not have to fill in the structural argument.
  3. [Section 2, Eq. (2) and the definition of g(θ)] The expression for g(θ) is typeset as 'g(θ) = 2−θ+ 2 θ', which appears to have lost a superscript; it should read g(θ) = 2 − θ + 2^θ. With the printed text, the claimed range [2.9, 3] is not reproducible.
  4. [Section 3, proof of Lemma 3.2] In the chain '|v|−1 ≤ ceil(n/2^d)−1 ≤ n/2^d', the final inequality is correct but not entirely immediate because of the ceiling; adding a short explanation such as 'for integer x, ceil(x)−1 ≤ x' would improve clarity.
  5. [Section 3, tightness example] The expression 'H=O(lgn/n)' is ambiguous; it should be written as H = O((log n)/n) or H = O(log n / n).

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof is a self-contained charging argument, with prior-work citations used only as background.

full rationale

The derivation is self-contained and parameter-free. The per-run decomposition in Eq. (1) is presented as an accounting identity derived from the recursion tree and the run partition; it is not defined in terms of the target bound. The central per-run estimate M(R) ≤ L(log2(n/L) + 3) is proved directly by the level-by-level charging argument, including the explicit inequality (*) and the g(θ) calculation, and the general-n case supplies its own Lemmas 3.1 and 3.2. The only citation near the proof is [lBW23, §3.3], which the paper explicitly labels as background ('The same calculation appears') and does not use in place of the reproduced calculation; it is therefore not load-bearing. No parameter is fitted to data, no prediction is a renamed input, and no uniqueness or ansatz is imported from the author's prior work. The skeptical observation that Eq. (1) may overcount under the sorted check is a correctness concern about an equality versus an upper bound, not a circularity: the upper-bound direction is all the theorem needs, and the charging scheme is still derived from the algorithm's recursion tree rather than from the claimed result. Hence there is no significant circularity.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

The proof is largely self-contained. The only structurally load-bearing assumption is the geometric fact that a contiguous run can intersect at most two subproblems at any depth of the recursion tree. All other ingredients are elementary or proved in the note. No free parameters are fitted, and no new entities are postulated.

assumptions (1)
  • domain assumption At any depth of the recursion tree, a single run can contribute to at most two subproblems.
    Used in Sections 2 and 3 to bound the charge per level by 2n/2^d. Follows from contiguity of runs and the recursion tree partition, but is not stated or proved as a formal lemma.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Top-Down Mergesort with Sorted Check Has Mergecost $\le(\mathcal H+3)n$." pith.science (2026). https://pith.science/paper/HUIGC6PQ

@misc{pith2026260808348,
  author       = {Pith},
  title        = {Pith review of: Top-Down Mergesort with Sorted Check Has Mergecost $\le(\mathcal H+3)n$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HUIGC6PQ}},
  note         = {Machine review of arXiv:2608.08348}
}
abstract

We consider standard top-down recursive Mergesort, where we do a single comparison before calling merge to check if the two recursively sorted subproblems happens to already be correctly ordered. (If so, we can skip the merging step). We show for any input $A[0..n)$ of elements consisting of $r$ runs (maximal increasing contiguous subranges in $A$) of respective lengths $L_1,\ldots, L_r$, the mergecost $M$ (the sum of output sizes of all merges) satisfies $M \le (\mathcal H+3)n$ for $\mathcal H = \sum_{i=1}^r (L_i / n) \log_2(n/L_i)$ the runlength entropy.

Figures

Figures reproduced from arXiv: 2608.08348 by the authors.

Figure 1
Figure 1. The recursion tree T of Mergesort on an input of size n = 100 and run lengths (L1, . . . , L7) = (15, 28, 1, 3, 17, 27, 9). Nodes v ∈ T that do not contain a run boundary are skipped (faded); only filled nodes contribute (their size) to the mergecost M = 394. arXiv:2608.08348v1 [cs.DS] 8 Aug 2026 [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. The recursion tree from [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 27 canonical work pages

  1. [1]

    European Symposium on Algorithms (ESA) , year =

    Funnelselect: Cache-oblivious multiple selection , author =. European Symposium on Algorithms (ESA) , year =. doi:10.4230/LIPIcs.ESA.2023.25 , pages =

    work page doi:10.4230/lipics.esa.2023.25 2023

  2. [2]

    Adaptive Shivers Sort: An Alternative Sorting Algorithm , volume =

    Jugé, Vincent , year =. Adaptive Shivers Sort: An Alternative Sorting Algorithm , volume =. ACM Transactions on Algorithms , publisher =. doi:10.1145/3664195 , number =

    work page doi:10.1145/3664195

  3. [3]

    Peters, Tim , year =

    work page

  4. [4]

    2009 , note =

    Analytic Combinatorics , author =. 2009 , note =

    work page 2009

  5. [5]

    Algorithmica , volume =

    Stefan Edelkamp and Armin Wei. Algorithmica , volume =

    work page

  6. [6]

    2019 , publisher =

    Efficient Second-Order Shape-Constrained Function Fitting , author =. 2019 , publisher =. doi:10.1007/978-3-030-24766-9_29 , url =

    work page doi:10.1007/978-3-030-24766-9_29 2019

  7. [7]

    arXiv , arxivId =:1908.00563 , year =

    Dynamic Optimality Refuted -- For Tournament Heaps , author =. arXiv , arxivId =:1908.00563 , year =

    arXiv 1908

  8. [8]

    Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space

    Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space , author =. arXiv , arxivId =:1903.02533 , year =

    work page Pith review arXiv 1903

Show all 29 references
  1. [9]

    Compressed Range-Minimum Queries and Binary Trees , author =

  2. [10]

    Nebel and Elisabeth Neumann and Sebastian Wild , booktitle =

    Markus E. Nebel and Elisabeth Neumann and Sebastian Wild , booktitle =. Median-of- k Jumplists and Dangling-Min. arXiv , primaryClass =:1609.08513 , year =

    arXiv

  3. [11]

    Meeting on Analytic Algorithmics and Combinatorics (ANALCO) , publisher =

    Sesquickselect: One and a half pivots for cache-efficient selection , author =. Meeting on Analytic Algorithmics and Combinatorics (ANALCO) , publisher =. arXiv , primaryClass =:1810.12322 , year =

    arXiv

  4. [12]

    arXiv , primaryClass =:1811.01259 , url =

    Stefan Edelkamp and Armin Wei. arXiv , primaryClass =:1811.01259 , url =

    arXiv

  5. [13]

    it - Information Technology , year =

    Dual-pivot and beyond: The potential of multiway partitioning in quicksort , author =. it - Information Technology , year =. doi:10.1515/itit-2018-0012 , sortyear =

    2018 doi

  6. [14]

    European Symposium on Algorithms (ESA) , pages =

    Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs , author =. European Symposium on Algorithms (ESA) , pages =. 2018 , volume =

    2018

  7. [15]

    Average Cost of

    Sebastian Wild , booktitle =. Average Cost of. 2018 , editor =. doi:10.4230/LIPIcs.AofA.2018.36 , url =

    2018 doi

  8. [16]

    Workshop on Analytic Algorithmics and Combinatorics (

    Quicksort Is Optimal For Many Equal Keys , author =. Workshop on Analytic Algorithmics and Combinatorics (. 2018 , publisher =. doi:10.1137/1.9781611975062.2 , sortyear =. arXiv , primaryClass =:1608.04906 , url =

    2018 arXiv

  9. [17]

    2015 , archivePrefix =

    A Practical and Worst-Case Efficient Algorithm for Divisor Methods of Apportionment , author =. 2015 , archivePrefix =. 1504.06475 , url =

    2015 arXiv

  10. [18]

    Algorithmica , year =

    Building Fences Straight and High: An Optimal Algorithm for Finding the Maximum Length You Can Cut k Times from Given Sticks , author =. Algorithmica , year =. arXiv , primaryClass =:1502.04048 , url =

    arXiv

  11. [19]

    2016 , isbn =

    Dual-Pivot Quicksort and Beyond: Analysis of Multiway Partitioning and Its Practical Potential , author =. 2016 , isbn =

    2016

  12. [20]

    and Wild, Sebastian and Mart

    Nebel, Markus E. and Wild, Sebastian and Mart. Analysis of Pivot Sampling in Dual-Pivot. Algorithmica , volume =. 2016 , url =. arXiv , primaryClass =:1412.0193 , doi =

    2016 arXiv

  13. [21]

    ACM Transactions on Algorithms , year =

    Average Case and Distributional Analysis of Dual Pivot Quicksort , author =. ACM Transactions on Algorithms , year =. arXiv , primaryClass =:1304.0988 , doi =

    arXiv

  14. [22]

    Analysis of Branch Misses in

    Conrado Mart. Analysis of Branch Misses in. 2015 , booktitle =. arXiv , primaryClass =:1411.2059 , doi =

    2015 arXiv

  15. [23]

    and Mahmoud, Hosam , journal=

    Wild, Sebastian and Nebel, Markus E. and Mahmoud, Hosam , journal=. Analysis of. 2016 , month=jan, volume=. arXiv , primaryClass =:1306.3819 , url =

    2016 arXiv

  16. [24]

    and Wild, Sebastian , booktitle =

    Nebel, Markus E. and Wild, Sebastian , booktitle =. Pivot Sampling in Dual-Pivot. arXiv , primaryClass =:1403.6602 , year =

    arXiv

  17. [25]

    and Reitzig, Raphael and Laube, Ulrich , booktitle =

    Wild, Sebastian and Nebel, Markus E. and Reitzig, Raphael and Laube, Ulrich , booktitle =. Engineering. 2013 , url =

    2013

  18. [26]

    , booktitle =

    Sebastian Wild and Nebel, Markus E. , booktitle =. Average Case Analysis of. 2012 , archivePrefix =. 1310.7409 , url =

    2012 arXiv

  19. [27]

    2012 , type =

    Sebastian Wild , institution =. 2012 , type =

    2012

  20. [28]

    Journal of Bioinformatics and Computational Biology , doi =

    Sebastian Wild and Markus Nebel and Michael Holzhauser and Lars H. Journal of Bioinformatics and Computational Biology , doi =. 2011 , month = dec, volume =

    2011

  21. [29]

    Sebastian Wild , year =. An

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.