Optimal Parallel Comparison Sorting for Up to 10 Elements on Up to 10 Processors

Abstract

We study the problem of parallel comparison sorting, modeled as a two-player game between a sorter and an adversary. Using a minimax algorithm enhanced with several domain-specific optimizations, we compute the exact minimal number of rounds [Formula: see text] required to sort [Formula: see text] elements using at most [Formula: see text] comparisons per round, for all [Formula: see text] and [Formula: see text]. The optimizations include canonical labelling of states, memoization, alpha–beta pruning, and an early-stopping rule exploiting the fact that candidate sorter moves can differ in value by at most one round. Together, these techniques make the computation feasible, and we measure the contribution of each of them. To our knowledge these are the first exact values of [Formula: see text] for the adaptive model. The results quantify the overhead of parallelism: no computed value exceeds the sequential-work lower bound [Formula: see text] by more than one round, yet parallel efficiency falls from [Formula: see text] at [Formula: see text] to [Formula: see text] at [Formula: see text] for [Formula: see text], because adversarial outcomes prevent perfect speedup.