Sorting Short Keys in Circuits of Size ${o(n \log n)}$
Sorting Short Keys in Circuits of Size ${o(n \log n)}$
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-standing open problem is whether there exist $(k + w) \cdot o(n \log n)$-sized Boolean circuits for sorting. A landmark result in …