language: en

Deterministic Sorting in Nearly Logarithmic Time on the Hypercube and Related Computers

Robert Cypher
IBM Almaden Research Center
650 Harry Rd. San Jose, CA 95120
C. Greg Plaxton
MIT Laboratory for Computer Science
545 Technology Square Cambridge, MA 02139
November 29, 1995

Abstract This paper presents a deterministic sorting algorithm, called Sharesort, that sorts n records on an n-processor hypercube, shu*e-exchange, or cube-connected cycles in O(log n (log log n) 2 ) time in the worst case. The algorithm requires only a constant amount of storage at each processor. The fastest previous deterministic algorithm for this problem was Batcher's bitonic sort, which runs in O(log 2 n) time.

[Supported by an NSERC postdoctoral fellowship, and DARPA contracts N00014-87-K-825 and N00014 89-J-1988.]