Sorting in One and Two Rounds using $t$-Comparators

Ran Gelles, Zvi Lotker, Frederik Mallmann-Trenn

We examine sorting algorithms for $n$ elements whose basic operation is comparing $t$ elements simultaneously (a $t$-comparator). We focus on algorithms that use only a single roun…