Abstract
We build boolean circuits of size 𝒪(nm2) and depth 𝒪(log(n) + m log(m)) for sorting n integers each of m-bits. We build also circuits that sort n integers each of m-bits according to their first k bits that are of size 𝒪(nmk (1 + log^*(n) - log^*(m))) and depth 𝒪(log3(n)).
This improves on the results of Asharov et al. [Asharov et al., 2021] and resolves some of their open questions.