Are there [good/optimal] parallel comparison sorts?

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.

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

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

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

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

Reference:

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

• 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.) $\;\;$ – user6973 Jun 17 '12 at 7:49

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?

• 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