Sorting Short Keys in Circuits of Size o(n log n)

Gilad Asharov, Wei-Kai Lin, Elaine Shi

We consider the classical problem of sorting an input array containing $n$ elements, where each element is described with a $k$-bit comparison-key and a $w$-bit payload. A long-sta…