Author(s)

A.W.S. Loo, R.W.M. Yip & C.W. Chung

Abstract

This paper presents a parallel sorting algorithm (introduced in [LoYi91]) that makes use of the statistical properties of the elements to be sorted. Experiments are run on a MIMD computer. The results suggest that the new algorithm out-performs the parallel quicksort. Similar findings are obtained from a prior study using simulation. Introduction Quicksort [Hoar61] is a popular sorting algorithm. It has average complexity of O(n log n), but its performance degenerates to O(n^) in the worst case when it divides a list of elements to be sorted into two uneven sized sublists which are to be sorted subsequently. Some proposals are raised to avoid the occurrence of the worst case [Erki84, Wain85] and improve the performance of quicksort [Sedg75, Sedg78, FrazTO], but some [Han91, NoA185, JanLamSS,

Keywords