๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Constant time parallel sorting: an empirical view

โœ Scribed by William Gasarch; Evan Golub; Clyde Kruskal


Book ID
104147696
Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
507 KB
Volume
67
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

โœฆ Synopsis


Consider the following problem: If you want to sort n numbers in k (a constant) rounds then how many comparisons-per-round do you need? This problem has been studied carefully and there exist several algorithms and some lower bounds for it. Many of the algorithms are non-constructive. We have embarked on an empirical study of most of the algorithms in the literature, including the non-constructive ones. This paper is an exposition of what we have found. One of our conclusions is that non-constructive algorithms can be useful.


๐Ÿ“œ SIMILAR VOLUMES