Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: Notesfiles $Revision: 1.6.2.13 $; site uiucdcs.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxl!ihnp4!inuxc!pur-ee!uiucdcs!kruskal
From: kruskal@uiucdcs.UUCP
Newsgroups: net.lang
Subject: More about fast parallel sorting - (nf)
Message-ID: <26400017@uiucdcs.UUCP>
Date: Tue, 26-Jun-84 04:06:00 EDT
Article-I.D.: uiucdcs.26400017
Posted: Tue Jun 26 04:06:00 1984
Date-Received: Thu, 28-Jun-84 04:51:49 EDT
Lines: 35
Nf-ID: #N:uiucdcs:26400017:000:1210
Nf-From: uiucdcs!kruskal    Jun 26 03:06:00 1984

#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