An efficient parallel sorting algorithm
type: Item
instance of: scholarly article
title: An efficient parallel sorting algorithm
zbMATH Open document ID: 0753.68033
DOI: 10.1016/0020-0190(92)90004-F
author: Xiaoqing Liu
author: Junguk L. Kim
published in: Information Processing Letters
publication date: 1993-01-16T00:00:00Z
review text: We consider the merge-based sorting on the EREW PRAM multiprocessor with private caches. We propose a parallel sorting algorithm that achieves linear speedup in both the number of comparisons and the number of data accesses, using a novel partition algorithm which splits an arbitrary number of sorted runs among all the processors evenly, independent of the sort-key value. The percentile point for each sorted run is found efficiently and only one merge pass is required. The processing and access costs are \(O(t_ p((N/P)\log N+P\log(N/(2P))))\) and \(O(t_ a((N/P)(\log(NM/P)/\log M)+P\log(N/(2P))))\), where \(N\) is the number of data elements, \(P\) is the number of processors, \(M\) is the size of the cache, \(t_ p\) is the time needed to execute an instruction using cache memory and \(t_ a\) is the time needed for a data access from shared memory.
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 94472
zbMATH Keywords: partitioning
zbMATH Keywords: merging
zbMATH Keywords: EREW PRAM
MaRDI profile type: Publication
cites work: On computing the closest boundary point on the convex hull
cites work: Geometric complexity of some location problems
full work available at URL: 0020-0190(92)90004-f
OpenAlex ID: W2321698191
description: scientific article; zbMATH DE number 94472