Deterministic sorting in nearly logarithmic time on the hypercube and related computers

Abstract

This paper presents a determinstic sorting algorithm, called Sharesort, that sorts n records on an n processor hypercube, shuffle-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 bitonic sort, which runs in O(log2 n) time.