Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Constant time parallel sorting: an empirical view
Gasarch W., Golub E., Kruskal C. Journal of Computer and System Sciences67 (1):63-91,2003.Type:Article
Date Reviewed: Nov 21 2003

It is well known that sorting a list of n elements is possible with O(n ˙ log n) comparisons. If we have several processors working in parallel, then we can sort n elements even faster. For example, if we have n(n-1)/2 processors, then we can make all the comparisons at once (that is, we can sort n elements in a single round of comparisons). It is possible to show that if we want to sort in one round, then we need at least n(n-1)/2 processors working in parallel. If we do not have that many processors, the next natural questions are: How many processors do we need to sort n elements in 2 rounds? In 3 rounds? In k rounds for a given value k? For this, it is known that we need at least O(n1+1/k ˙ (log n)1+1/k) processors, and that we can sort in k rounds if we have O(n1+1/k ˙ (log n)2-1/k) processors. The existence of such k-round sorting is proven nonconstructively, by showing that such a sorting must exist. If we restrict ourselves only to efficient (polynomial-time computable) sorting schemes, then the best known k-round sorting algorithms require slightly more, namely, O(n1+1/k+o(1)) processors. If we use randomized methods, then it is possible to sort using only O(n1+1/k) processors.

Gasarch, Golub, and Kruskal survey the existing lower and upper bounds and the corresponding algorithms, and they also provide an experimental comparison of different algorithms. The authors describe, for real n and k, which algorithms are empirically better. Some conclusions of their experimental analysis are as anticipated: factors of log log n do not usually affect the algorithm’s performance; more complex algorithms that are asymptotically better behave worse for small n. However, there is one somewhat unexpected conclusion: nonconstructive algorithms often perform as well as constructive ones, and sometimes even better. A reason for this may be that the existence theorems behind nonconstructive algorithms are usually proven by showing that almost all graphs with a certain property lead to fast sorting; so, we can often use random number generators to generate random graphs with these properties, and, in these cases, the graphs lead to well-performing sortings.

Reviewer:  V. Kreinovich Review #: CR128624 (0404-0463)
Bookmark and Share
  Featured Reviewer  
Sorting/ Searching (E.5 ... )
Graph Algorithms (G.2.2 ... )
Graph And Tree Search Strategies (I.2.8 ... )
Problem Solving, Control Methods, And Search (I.2.8 )
Files (E.5 )
Would you recommend this review?
Other reviews under "Sorting/Searching": Date
New techniques for best-match retrieval
Shasha D. (ed), Wang T. ACM Transactions on Information Systems 8(2): 140-158, 2001. Type: Article
Jun 1 1991
An adaptation of a root finding method to searching ordered disk files
Armenakis A., Garey L., Gupta R. BIT 25(4): 562-568, 1985. Type: Article
Mar 1 1987
Approximating shortest superstrings with constraints
Jiang T., Li M. (ed) Theoretical Computer Science 134(2): 473-491, 1994. Type: Article
Nov 1 1995

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2023 ThinkLoud®
Terms of Use
| Privacy Policy