Efficient deterministic sorting on the BSP model

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


We present a new algorithm for deterministic sorting on the Bulk-Synchronous Parallel (BSP) model of computation. We sort n keys using a partitioning scheme that achieves the requirements of efficiency (one-optimality) and insensitivity against initial key distribution. Although we employ sampling to realize efficiency, we give a precise worst-case estimation of the maximum imbalance which might occur. The algorithm is one-optimal for a wide range of the BSP parameters in the sense that its speedup on p processors is asymptotically (1 - o(1)) p.

Original languageEnglish (US)
Pages (from-to)69-79
Number of pages11
JournalParallel processing letters
Issue number1
StatePublished - 1999
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture


Dive into the research topics of 'Efficient deterministic sorting on the BSP model'. Together they form a unique fingerprint.

Cite this