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