10
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 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, 2013 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, 2013 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, 2013 at 15:37
  • 9
    $\begingroup$ I think the technical term for what you call blind sorting is oblivious "sorting network". $\endgroup$
    – Kaveh
    Oct 11, 2013 at 15:41

1 Answer 1

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 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, 2013 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.