Fast sorting algorithms on a linear array with a reconfigurablepipelined bus system |
| |
Authors: | Datta A Soundaralakshmi S Owens R |
| |
Affiliation: | Dept. of Comput. Sci. & Software Eng., Univ. of Western Australia, Perth, WA; |
| |
Abstract: | We present two fast algorithms for sorting on a linear array with a reconfigurable pipelined bus system (LARPBS), one of the recently proposed parallel architectures based on optical buses. In our first algorithm, we sort N numbers in O(log N log log N) worst-case time using N processors. In our second algorithm, we sort N numbers in O((log log N)2) worst-case time using N1+ε processors, for any fixed ε such that 0 < ε < 1. Our algorithms are based on a novel deterministic sampling scheme for merging two sorted arrays of length N each in O(log log N) time on an LARPBS with N processors. To our knowledge, the previous best sorting algorithm on this architecture has a running time of O((log N)2) using N processors |
| |
Keywords: | |
|
|