Fast sorting algorithms on a linear array with a reconfigurable pipelined bus system

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 V 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+epsilon processors, for any fixed epsilon such that 0<epsilon<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.