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?

  • $\begingroup$ As side note, sorting is $\mathsf{TC^0}$-complete. $\endgroup$
    – Kaveh
    Feb 24, 2013 at 4:56

2 Answers 2


(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 http://archive.org/details/tightcomparisonb00azar (June 17, 2012)

  • $\begingroup$ Could you give a more complete reference (authors, conference/journal, date, URL, etc.)? $\endgroup$
    – Jeffε
    Jun 17, 2012 at 1:26
  • $\begingroup$ Done. $\:$ (Well, I think that's good enough.) $\;\;$ $\endgroup$
    – user6973
    Jun 17, 2012 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?

  • 1
    $\begingroup$ I hope you'll find this non-post in this non-forum to be a valuable non-contribution ;-) $\endgroup$ Feb 23, 2013 at 11:38

Your Answer

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