# Complexity of blind sort?

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?

• What's your background? did you search around it? e.g bionic sorter gives a good network with size $O(n\cdot {\log^2 n})$, and time for creating corresponding network is at most as size of the network. – Saeed Oct 11 '13 at 15:09
• My background is in cryptography and I'm looking at sorting secret-shared data, which gives some rather unusual constraints on the relative cost of operations. I'm wondering whether I have hit an edge case where n^2 is a lower bound or whether it can't be brought down to the usual n log n after all - just checking to see if there's any situations where a higher bound such as n^2 is already known. – Bristol Oct 11 '13 at 15:23
• Actually by background I mean, because here people are trying to ask research level questions, so when you provide just a very naive approach means there is not much research behind the question, may be some other sites is better suited for this. – Saeed Oct 11 '13 at 15:37
• I think the technical term for what you call blind sorting is oblivious "sorting network". – Kaveh Oct 11 '13 at 15:41

• I think bitonic sort is not as impractical, but it's $O(n\log^2 n)$. THe AKS sorting network is definitely impractical. – David Eppstein Nov 7 '13 at 8:01