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 Sciences 67 (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
 BlockQuicksort: avoiding branch mispredictions in Quicksort
Edelkamp S., Weiß A.  Journal of Experimental Algorithmics 24(1): 1-22, 2019. Type: Article
Apr 1 2022
Community search over big graphs
Huang X., Lakshmanan L., Xu J.,  Morgan&Claypool Publishers, San Rafael, CA, 2019. 208 pp. Type: Book (978-1-681735-95-5)
Dec 19 2019
Centrality and diversity in search: roles in A.I., machine learning, social networks, and pattern recognition
Murty M., Biswas A.,  Springer International Publishing, New York, NY, 2019. 94 pp. Type: Book (978-3-030247-12-6)
Dec 10 2019

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2022 ThinkLoud, Inc.
Terms of Use
| Privacy Policy