[net.lang] More about fast parallel sorting

kruskal@uiucdcs.UUCP (06/26/84)

#N:uiucdcs:26400017:000:1210
uiucdcs!kruskal    Jun 26 03:06:00 1984

The "fastest" known parallel sorting algorithm is O(log N).
It works on a sorting network of size O(N log N), and was invented by
Ajtai, Komlos, and Szemeredi (15th Annual Sigact, 1983).
Admittedly, it has a very very large constant factor.

This leads to an O(log N) parallel sorting algorithm for a 
machine with N processors, each connected to a constant
number of neighbors (Leighton, Sigact, 1984).
The constant factor is still very very large.

For a "shared memory" model of parallel computation,
there exists an algorithm for N processors that
takes about 1.893 (log N) (log log N) / (log log log N)
comparison steps.  (Logs are base 2.)

If one generalizes the top two in the "right" way,
for P processors, N items, and N>=P, they will run in
O(N (log N) / P), i.e. they have provably optimal
speedup (up to a very very large constant factor).

Conservatively, the bottom one will take
N (log N) / P   +   1.893 (log P) (log log P) / (log log log P)
   +   O( N/P + (log P) log(2N/P) )
comparison steps.  It is optimal up to a constant factor
for N >= P log log P (I think), and the constant is not
absurdly large.



			Clyde P. Kruskal
			University of Illinois
			USENET: ...pur-ee!uiucdcs!kruskal