Search
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)
 Would you recommend this review? yes no
 Other reviews under "Sorting/Searching": Date BlockQuicksort: avoiding branch mispredictions in QuicksortEdelkamp S., Weiß A.  Journal of Experimental Algorithmics 24(1): 1-22, 2019. Type: Article Apr 1 2022 Community search over big graphsHuang 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 recognitionMurty M., Biswas A.,  Springer International Publishing, New York, NY, 2019. 94 pp. Type: Book (978-3-030247-12-6) Dec 10 2019 more...

E-Mail This Printer-Friendly
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2022 ThinkLoud, Inc.