Paper Info
Title
A tighter upper bound on the worst case behavior of Conway's parallel sorting algorithm
Abstract
We analyze the worst case behavior of a parallel sorting algorithm, attributed to Conway, that uses a linear array of n − 1 finite state machines to sort n keys. Warshauer (J. Algorithms7 (1986), 270–276) shows that the algorithm requires at most 2n − 3 iterations of the outer loop to sort all keys, and he exhibits a class of inputs for which [4n3] − 1 iterations are required. We improve the upper bound to 4n3 + O(1) for all inputs and any n matching Warshauer's lower bound to within an additive constant.
Year
DOI
Venue
1988
10.1016/0196-6774(88)90024-7
J. Algorithms
Keywords
Field
DocType
worst case behavior,upper bound
Discrete mathematics,Combinatorics,Algorithmics,Algorithm complexity,Upper and lower bounds,Parallel algorithm,sort,Algorithm,Finite-state machine,Sorting,Parallel sorting,Mathematics
Journal
Volume
Issue
ISSN
9
3
0196-6774
Citations 
PageRank 
References 
0
0.34
1
Authors
1
Name
Order
Citations
PageRank
Alejandro A. Schäffer1827136.66