Randomized sorting algorithm on the BSP model

Alexandros V. Gerbessiotis, Constantinos J. Siniolakis

Research output: Contribution to journalConference articlepeer-review

7 Scopus citations


We present a new randomized sorting algorithm on the Bulk-Synchronous Parallel (BSP) model. The algorithm improves upon the parallel slack of previous algorithms to achieve optimality. Tighter probabilistic bounds are also established. It uses sample sorting and utilizes recently introduced search algorithms for a class of data structures on the BSP model. Moreover, our methods are within a 1+o(1) multiplicative factor of the respective sequential methods in terms of speedup for a wide range of the BSP parameters.

Original languageEnglish (US)
Pages (from-to)293-297
Number of pages5
JournalProceedings of the International Parallel Processing Symposium, IPPS
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1997 11th International Parallel Processing Symposium, IPPS 97 - Geneva, Switz
Duration: Apr 1 1997Apr 5 1997

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture


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

Cite this