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) • o(n log n)-sized boolean circuits for sorting. A landmark result in this area is the work by Ajtai, Komlós, and Szemerédi (STOC'83), where they showed how to achieve sorting circuits with (k + w) • O(n log n) boolean gates. The recent work of Farhadi et al. (STOC'19) showed that if the famous Li-Li network coding conjecture is true, then sorting circuits of size w • o(n log n) do not exist for general k; however, no unconditional lower bound is known (in fact proving super-linear circuit lower bounds in general is out of the reach of existing techniques).

In this paper, we show that one can overcome the n log n barrier when the keys to be sorted are short. Specifically, we prove that there is a circuit with (k + w) • O(nk) • poly(log * nlog * (w + k)) boolean gates capable of sorting any input array containing n elements, each described with a k-bit key and a w-bit payload. Therefore, if the keys to be sorted are short, say, k < o(log n), our result is asymptotically better than the classical AKS sorting network (ignoring poly log * terms); and we also overcome the n log n barrier in such cases. Such a result might be surprising initially because it is long known that comparator-based techniques must incur Ω(n log n) comparator gates even when the keys to be sorted are only 1-bit long (e.g., see Knuth's "Art of Programming" textbook). To the best of our knowledge, we are the first to achieve non-trivial results for sorting circuits using non-comparison-based techniques. We also show that if the Li-Li network coding conjecture is true, our upper bound is optimal, barring poly log * terms, for every k as long as k = O(log n).