# Parallel Sorting Algorithms

Florent Dupont de Dinechin and Helmut Weberpals

Research period: 1993-1995

Sorting belongs to the best understood problems in the field of sequential computing. In parallel computing, however, the sorting network proposed by Ajtai et al. as well as Cole's sorting algorithm achieve optimum time complexity but with constants so large that these are mainly of theoretical interest.

Our approach differs from previous work in that we intend
to sort n keys using p processors in case p << n
which is of practical importance.
Our algorithm is derived from the merge sort algorithm and exploits the
Concurrent-Read and Exclusive-Write Parallel Random Access Machine model
of parallel computation.
It sorts n keys using p processors in asymptotically optimum time
O((n log(n))/p) provided p log(p) ≤ n
and approaches the time complexity O((log(n))^{2})
of Batcher's bitonic sorting algorithm when p tends to n/2.