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
• DOI: 10.1016/s0022-0000(03)00040-0

✦ 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.