Deterministic sorting in nearly logarithmic time on the hypercube and related computers
Robert Cypher, C. Gregory Plaxton · 1990
This paper presents a deterministic sorting algorithm, called Sharesort, that sorts n records on an n processor hypercube, shuffle-exchange or cube-connected cycles in O(log n(loglog 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 bitonic sort [3], which runs in O(log 2 n) time.