Optimal Parallel Comparison Sorting for Up to 10 Elements on Up to 10 Processors
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 mos...