Mean-Partition Sorting Revisited: Tight Worst-Case Bounds, an Entropy Decomposition, and a Safeguarded Variant

The arithmetic mean is an attractive partition threshold because it can be computed in a single scan and typically lies near the center of common numeric distributions. This study analyzes a canonical recursive mean-partition sorting algorithm for finite, totally ordered numeric inputs. It establishes correctness and termination, constructs an explicit geometric input family that forces splits of sizes (m−1, 1) at each recursive call, and derives a tight worst-case bound of Θ(n²), with exactly n(n+1)/2−1 threshold comparisons under the specified scan model. The analysis further derives an exact entropy decomposition of the total partition-scanning cost. For distinct keys, the cost is n log₂ n plus a nonnegative weighted entropy-deficit term; for multisets, the baseline becomes nH(q), where q denotes the empirical key-frequency distribution. The study also introduces Entropy-Guarded Mean-Partition Sort, which accepts a mean split only when its binary entropy exceeds a fixed threshold; otherwise, it invokes a deterministic O(m log m) fallback, ensuring a deterministic O(n log n) running-time guarantee. Exhaustive verification encompasses all 488,281 arrays of length at most eight over a five-value alphabet, supplemented by instrumented experiments on representative distributions. This record includes the manuscript, LaTeX source, reference implementation, experiment scripts, figures, and raw operation-count data.