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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Saeed Oct 11 '13 at 15:09
  • $\begingroup$ 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. $\endgroup$ – user17966 Oct 11 '13 at 15:23
  • $\begingroup$ 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. $\endgroup$ – Saeed Oct 11 '13 at 15:37
  • 9
    $\begingroup$ I think the technical term for what you call blind sorting is oblivious "sorting network". $\endgroup$ – Kaveh Oct 11 '13 at 15:41

Goodrich's "Randomized Shellsort: A Simple Oblivious Sorting Algorithm" has a discussion of data-oblivious sorting. Sorting networks are data-oblivious, but impractical in general, as I understand it.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy