Are there [good/optimal] parallel comparison sorts?

Question

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?

Answer 1

(answering my own question)

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

Answer 2

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?