Łukasz Skonieczny

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 [...