The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes

Abstract

Previous work identifying depth-optimal $n$-channel sorting networks for $9\le n\le 16$ is based on exploiting symmetries of the first two layers. However, the naive generate-and-test approach typically applied does not scale. This paper revisits the problem of generating two-layer prefixes modulo symmetries. An improved notion of symmetry is provided and a novel technique based on regular languages and graph isomorphism is shown to generate the set of non-symmetric representations. An empirical evaluation demonstrates that the new method outperforms the generate-and-test approach by orders of magnitude and easily scales until $n=40$.

Cited by in corpus (7)

• Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten)
• Sorting Networks: to the End and Back Again
• Optimal-Depth Sorting Networks
• Applying Sorting Networks to Synthesize Optimized Sorting Libraries
• Sorting Networks: the End Game
• Faster Sorting Networks for $17$, $19$ and $20$ Inputs
• Sorting Networks: The Final Countdown