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