= Solution
Apply <comparator composition> recursively in a <balanced binary tree>, with one-<bit> <digital comparators> at its leaves. For a <power of two> $n$, the <circuit size> and <circuit depth> satisfy
$$
S(n)=2S(n/2)+O(1),\qquad D(n)=D(n/2)+O(1).
$$
There are $n$ leaves and $n-1$ internal nodes, so \b[the <circuit size> is $O(n)$ and the combinational delay is $O(\log n)$]. Here each fixed-fan-in <logic gate> has bounded delay. For arbitrary $n$, pad both inputs with leading zero <bits> to the next <power of two>, which is less than $2n$; this preserves their <unsigned interpretation> and both bounds.
Back to article page
