We all know that the minimal complexity of a comparison-based sorting algorithm is $\Omega(n \log n)$ comparisons. I'm trying to do a blind sort, i.e. given a number $n$ output a circuit (with boolean, arithmetic and "comparison" gates) that sorts a list of $n$ items.
Precomputing all ${n \choose 2}$ comparisons and then doing arithmetic on the resulting bits gets me an $\Theta(n^3)$ algorithm, however by some crazy "pointer arithmetic" I think I can get a $\Theta(n^2)$ version.
Is there a known lower bound for comparison-based sorting circuits along similar lines to the $n \log n$ one for comparison-based sorting algorithm? Might it even be possible to blind sort in $n \log n$ time?
n^2
is a lower bound or whether it can't be brought down to the usualn log n
after all - just checking to see if there's any situations where a higher bound such asn^2
is already known. $\endgroup$