Sorting Short Integers

Michal Koucký, Karel Král

We build boolean circuits of size $O(n{m}^2)$ and depth $O(\log (n)+m\log (m))$ for sorting $n$ integers each of $m$-bits. We build also circuits that sort $n$ integers each of $m$-…