{"id":"912bb942-125d-407a-acd6-740e237de5c3","arxiv_id":"2608.08348","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Top-down Mergesort with a sorted check before each merge has merge cost M ≤ (H+3)n for any input, where H is the run-length entropy.","lead":"Standard top-down Mergesort can be made run-adaptive with a single extra comparison that skips merging when the two sorted halves are already in order. This note proves this simple variant has merge cost at most (H+3)n, where H is the run-length entropy, nearly matching the optimal (H+2)n achieved by more complex algorithms.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Equation (1) is false as stated: the sorted check can skip merges at nodes counted in the per-run decomposition, so the proof needs an inequality instead of an equality.","rationale":"The reader's weakest_assumption concerns the unproved 'at most two contributing nodes per depth' structural fact. I examined this fact and it is true: at any fixed depth the recursion tree partitions [0,n) into contiguous intervals, so a contiguous run can intersect only the left- and right-boundary nodes that are not subsets of the run, giving at most two contributors. This is a minor expository gap, not a threat to the central claim. The more concrete and load-bearing issue is Eq (1), which the reader mentioned in the rationale but did not select as the weakest assumption. Eq (1) is stated as an equality but is actually an overcount, as shown by the n=3 example [1,3,2] where the root merge is skipped despite the root containing both runs. This does not invalidate the theorem because the proof only needs an upper bound, and the actual merge nodes are a subset of the nodes counted in Eq (1). The paper should replace the equality with an inequality and add a one-sentence justification. Therefore the reader's CONDITIONAL verdict is appropriate, and my stress-test does not move it.","tokens_in":2878,"tokens_out":25946,"duration_ms":213885,"concrete_test":"Write a brute-force checker for n=3..8 that enumerates all arrays (or all run-length partitions and all possible placements) and computes: (a) the actual mergecost M of the described algorithm, (b) the RHS of Eq (1), and (c) the bound (H+3)n. Verify that M ≤ (H+3)n in every case and that the RHS of Eq (1) is ≥ M, with strict inequality for at least one case (e.g., A=[1,3,2]). This confirms the theorem while exposing the false equality.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Equation (1) asserts M = Σ_i M(R_i) with M(R_i) = Σ_{v: R_i⊊v or v□□R_i} |v∩R_i|. This is not an equality for the algorithm with the sorted check. The merge at v is skipped when A[m-1] ≤ A[m] after the recursive calls, which can happen even when v is not a subset of a single run. Example: n=3, A=[1,3,2]. The runs are R1=[0,2) (length 2) and R2=[2,3) (length 1). The root v=[0,3) has R1⊊v and R2⊊v, so Eq (1) charges 3. But the recursion sorts the right half to [2,3], then A[0]=1 ≤ A[1]=2, so the root merge is skipped; the only merge is inside the right half, output size 2. Hence Eq (1) overcounts. The rest of the proof only needs the upper bound, and actual merge nodes are a subset of the counted nodes, so the theorem M ≤ (H+3)n survives, but Eq (1) must be labelled as an inequality (or replaced by '≤'). This is a minor but real correctness issue in the written proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":3118,"tokens_out":13388,"duration_ms":115396,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Section 1, Eq. (1)"},{"comment":"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.","section":"Section 2, paragraph after Eq. (1)"},{"comment":"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.","section":"Section 2, Eq. (2) and the definition of g(θ)"},{"comment":"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.","section":"Section 3, proof of Lemma 3.2"},{"comment":"The expression 'H=O(lgn/n)' is ambiguous; it should be written as H = O((log n)/n) or H = O(log n / n).","section":"Section 3, tightness example"}],"recommendation":"minor_revision","confidential_remarks":"This is a short, self-contained theoretical note. The only substantive correctness issue is the mis-stated equality in Eq. (1), which is easily corrected and does not affect the central claim. The paper fits the scope of a theory journal or a note venue; I see no problems with novelty or citation practice."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper proves the folklore bound M ≤ (H+3)n for the standard top-down Mergesort with the sorted-check optimization. That specific bound for this specific algorithm is new, and the proof is mostly clean. The core sum inequality comes from Brodal–Wild (ESA 2023), which the paper cites, but the application to top-down Mergesort and the rounding lemmas for general n are the author's own contribution. The level-by-level charging argument is straightforward and sound, the Double Ceiling lemma is a neat observation, and the example showing the bound is asymptotically tight is helpful.\n\nThe soft spot is Equation (1). It asserts M = ∑ M(R_i), but that is not an equality for the algorithm with the sorted check. The sorted check can skip merges at nodes that the per-run decomposition counts. The stress-test example works: for A=[1,3,2], the runs are [0,2) and [2,3), and the root merge is skipped because A[0]≤A[1] after the recursion sorts the right half. Equation (1) charges 5, while the actual mergecost is 2. The theorem survives because the proof only needs an upper bound, and skipping merges only reduces cost, so writing M ≤ ∑ M(R_i) is fine. But the paper should label Equation (1) as an inequality, or at least say it is an upper-bound decomposition. This is minor and easily fixed, but it is a real correctness issue in the written proof.\n\nA second, smaller point: the claim that a run contributes to at most two nodes at each depth is used but never stated as a lemma. It is true because the recursion tree partitions the array into contiguous intervals, so it is not a serious gap, but making it explicit would help.\n\nThe citation pattern is fine. The lBW23 reference for the sum inequality is legitimate, and the calculation is reproduced, so there is no hidden dependency. The paper is self-contained and parameter-free.\n\nThis is a small but solid theoretical result. It will not change practice, but it settles a folklore bound for a widely used optimization. The intended audience is people working on sorting algorithms and run-adaptive analysis. I would send it to a serious referee; a competent referee will catch Equation (1) and request the trivial fix. After that, it is publishable as-is or with a short revision.","headline":"Correct folklore bound for Mergesort with sorted check, but Equation (1) is an inequality, not an equality.","tokens_in":3636,"tokens_out":2551,"would_cite":true,"duration_ms":22686,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W40","68P10"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["mergesort","run-adaptive sorting","mergecost","run-length entropy","sorted check","top-down recursion","entropy bounds","adaptive sorting analysis"],"falsifier":"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.","tokens_in":2672,"feed_emoji":"⚙️","tokens_out":12171,"duration_ms":96972,"temperature":0.7,"pith_summary":"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.","feed_headline":"Sorted-check mergesort proves mergecost ≤ (entropy+3)n","feed_subtitle":"One extra comparison per merge yields provable run-adaptivity, nearly matching run-adaptive sorters.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the run-length entropy lower bound $Hn$ and the $(H+2)n$ guarantee of run-adaptive mergesorts that this paper's bound is compared against.","marker":"[MW18]"},{"why":"Provides the summation inequality used to bound $\\sum \\min\\{L, 2n/2^d\\}$ in the per-run proof.","marker":"[lBW23]"},{"why":"Another run-adaptive mergesort achieving $(H+2)n$, serving as a comparison point for the constant 3.","marker":"[Jug24]"}],"fun_headline_variants":["Sorted-check Mergesort: mergecost ≤ (entropy+3)n","One comparison per merge proves run-adaptive mergecost","Entropy-tight mergecost bound for Mergesort's sorted check","Skipping sorted subarrays: Mergesort hits (H+3)n mergecost"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Sorted-check Mergesort: mergecost ≤ (entropy+3)n","One comparison per merge proves run-adaptive mergecost","Entropy-tight mergecost bound for Mergesort's sorted check","Skipping sorted subarrays: Mergesort hits (H+3)n mergecost"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000266,"raw_usage":{"total_tokens":1602,"prompt_tokens":931,"completion_tokens":671,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":547,"completion_tokens_details":{"reasoning_tokens":591}},"tokens_in":547,"tokens_out":671,"duration_ms":7095,"temperature":1.0,"reasoning_tokens":591,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T00:08:03.575381+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}