[net.lang] Fastest parallel Sort

ech@spuxll.UUCP (Ned Horvath) (06/18/84)

The fastest known parallel sort uses the Batcher net and operates in time
O((log n)^2).  That is also known to be optimal for a general (i.e. not
data-dependent) sorting algorithm. As usual, see Knuth, v. 3, for details.


=Ned=

dkit@whuxk.UUCP (LIPINSKI) (06/22/84)

The fastest parallel sort has recently been proved to be O(log n),
which improves upon Batcher's O((log n)^2).  It's in a paper by
Komlos, Ajtai, and Sar??? (sp) [Stanford &/| UCSD], and it uses
expander graphs and a linear nearsort algorithm.  The problem is
that the linear coefficient is huge (10^20?), so it's no good to
actually implement it; it just proved it can be done in O(log n).

						Michael Baldwin
						{harpo,ihnp4}!whuxg!mike