The Parallel Computing Group

• Address
• Research
• Teaching
• Who is Who
• Impressum
• > TUHH

Last modified on
15 February 2006

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))²) of Batcher's bitonic sorting algorithm when p tends to n/2.