Abstract:We investigate how sorting algorithms navigate the complexity of permutation space. Our main contribution is a continuous-time geometric model that casts sorting as directed motion on the permutohedron. A quadratic potential generates an ambient gradient flow that contracts toward the fixed sorted vertex $v_s=(1,2,\ldots,n)$. This dynamical picture is set against two discrete descriptions of the same problem. One follows adjacent-swap paths along the $1$-skeleton, while the other uses comparison half-spaces to refine the feasible order types. Together, they provide the combinatorial foils used to evaluate the continuous trajectory. Comparisons remove informational ambiguity, whereas the flow removes metric distance. The two mechanisms are complementary. To support this analysis, we present decision-tree arguments and local paths with $\Theta(n^2)$ behavior. We also show that the quadratic potential decreases strictly under every inversion-removing adjacent swap and formulate global half-space constraints on candidate rank maps. The maximal fixed-threshold relaxation time is determined exactly by the Euclidean diameter of the permutohedron, and the product of this relaxation time with the dimension is $\Theta(n\log n)$. Under a normalized comparison clock, this intrinsic geometric quantity has the same asymptotic scale as classical optimal comparison sorting.
From: Jonathan Landers [view email]
[v1]
Wed, 23 Apr 2025 13:38:00 UTC (325 KB)
[v2]
Wed, 22 Jul 2026 13:50:15 UTC (225 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。