An efficient parallel sorting algorithm (Q1199552)

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.