Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Comparing each pair of elements and sorting according to
[[number less than] minus [number greater than]] is a parallel comparison
sorting algorithm with a depth of $1$ comparison and $O\left(n^2\right)$ total comparisons.

By the AKS network, there is a parallel comparison sorting algorithm with
a depth of $O(\log(n))$ comparisons and $O(n\cdot \log(n))$ total comparisons.

Are there any parallel comparsion sorts with a depth of
$o(\log(n))$ comparisons and $o\left(n^2\right)$ total comparisons?

Are there any parallel comparison sorts with a depth
of $1$ comparison and $O(n\cdot \log(n))$ total comparisons?

share|cite|improve this question
As side note, sorting is $\mathsf{TC^0}$-complete. – Kaveh Feb 24 '13 at 4:56
up vote 5 down vote accepted

(answering my own question)

1. $\:$ Yes
2. $\:$ No


Tight Comparison Bounds On The Complexity Of Parallel Sorting
by Yossi Azar , Uzi Vishkin (1987)
publisher: Courant Institute of Mathematical Sciences, New York University
retrieved from (June 17, 2012)

share|cite|improve this answer
Could you give a more complete reference (authors, conference/journal, date, URL, etc.)? – Jeffε Jun 17 '12 at 1:26
Done. $\:$ (Well, I think that's good enough.) $\;\;$ – Ricky Demer Jun 17 '12 at 7:49

Please help me understand the model. I think it is equivalent to the following:

There is an array $A$ contained within a comparison oracle $O$ which you can send any list of pairs $[(i_1, j_1), \ldots, (i_n, j_n)]$ and which responds with a list of booleans $[b_1, \ldots, b_n]$ such that $b_k = 1 \iff A[i_k] > A[j_k]$, i.e. if the $k$'th pair represents an inversion.

A sorting algorithm is correct if it outputs $i_1, \ldots, i_n$ such that querying $O$ with $[(i_1, i_2), (i_2, i_3), \ldots, (i_{n-1}, i_n)]$ produces $[0, \ldots, 0]$, i.e. the output is sorted.

The performance of such an algorithm is measured by how many queries it performs to the oracle (depth) and the total number of pairs submitted to the oracle (the number of comparisons).

Your question is about the existence of thus defined correct sorting algorithms which satisfy various performance bounds.

Is this correct?

Sorting networks are thus a special case where each element may only occur once in each submitted batch of comparisons, as I understand it. Lifting this restriction is then the reason you can beat the performance of the best sorting networks. Agreed?

share|cite|improve this answer
I hope you'll find this non-post in this non-forum to be a valuable non-contribution ;-) – Jonas Kölker Feb 23 '13 at 11:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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