  A long-standing open question in the algorithms and complexity literature is
whether there exist sorting circuits of size $o(n \log n)$. A recent work by
Asharov, Lin, and Shi (SODA'21) showed that if the elements to be sorted have
short keys whose length $k = o(\log n)$, then one can indeed overcome the
$n\log n$ barrier for sorting circuits, by leveraging non-comparison-based
techniques. More specifically, Asharov et al.~showed that there exist $O(n)
\cdot \min(k, \log n)$-sized sorting circuits for $k$-bit keys, ignoring
$poly\log^*$ factors. Interestingly, the recent works by Farhadi et al.
(STOC'19) and Asharov et al. (SODA'21) also showed that the above result is
essentially optimal for every key length $k$, assuming that the famous Li-Li
network coding conjecture holds. Note also that proving any {\it unconditional}
super-linear circuit lower bound for a wide class of problems is beyond the
reach of current techniques.
  Unfortunately, the approach taken by Asharov et al.~to achieve optimality in
size somewhat crucially relies on sacrificing the depth: specifically, their
circuit is super-{\it poly}logarithmic in depth even for 1-bit keys. Asharov et
al.~phrase it as an open question how to achieve optimality both in size and
depth. In this paper, we close this important gap in our understanding. We
construct a sorting circuit of size $O(n) \cdot \min(k, \log n)$ (ignoring
$poly\log^*$ terms) and depth $O(\log n)$. To achieve this, our approach
departs significantly from the prior works. Our result can be viewed as a
generalization of the landmark result by Ajtai, Koml\'os, and Szemer\'edi
(STOC'83), simultaneously in terms of size and depth. Specifically, for $k =
o(\log n)$, we achieve asymptotical improvements in size over the AKS sorting
circuit, while preserving optimality in depth.
