A note on adaptive parallel sorting (Q582114)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A note on adaptive parallel sorting |
scientific article; zbMATH DE number 4130038
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on adaptive parallel sorting |
scientific article; zbMATH DE number 4130038 |
Statements
A note on adaptive parallel sorting (English)
0 references
1989
0 references
We present a cost optimal parallel algorithm for sorting presorted sequences. The measure of presortedness we consider is Rem, i.e., the smallest number of elements whose removal leaves a sorted sequence. The algorithm sorts a sequence X of length n, with \(Rem(X)=r\), in O(log n) time, provided \(O((n+r \log r)/\log n)\) processors are available, in the EREW PRAM model. This is the first PRAM sorting algorithm which is cost optimal with respect to Rem.
0 references
presortedness
0 references
EREW PRAM
0 references
sorting algorithm
0 references
0.95096666
0 references
0.9197073
0 references
0.9026769
0 references
0 references
0.89310396
0 references
0.89200425
0 references
0.8919941
0 references
0.88969475
0 references
