9
$\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?

$\endgroup$
  • 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$ – Bristol 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
14
$\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.

$\endgroup$
  • 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

Not the answer you're looking for? Browse other questions tagged or ask your own question.