|
Abstract : |
This paper presents deterministic algorithms for sorting n records on a p processor hypercube, shuffle-exchange or cube-connected cycles computer when n p. The fastest known deterministic sorting algorithm running on any of these computers for the case n = p is Sharesort, which runs in O(log n(log log n) 2) time in the worst case. An important subroutine in Sharesort solves a problem called shared key sorting. This paper presents new techniques for shared key sorting. These techniques yield algorithms for the sorting problem that are faster than all previously known algorithms over a wide range of the ratio n=p. Specifically, the techniques described in this paper yield 1) a relatively simple sorting algorithm that runs in O((n=p) log n(log log n \Gamma log log(2n=p)) + log 3, |
