Document Type
Report
Date
1-1991
Keywords
ISR-PRAM, Lexicographic Sorting, Parallel Algorithms, Parallel Processing, PRAM, R-PRAM, Sorting
Language
English
Disciplines
Computer Sciences
Description/Abstract
Though non-comparison based sorting techniques like radix sorting can be done with less "work" than conventional comparison-based methods, they are not used for long keys. This is because even though parallel radix sorting algorithms process the keys in parallel, the symbols in the keys are processed sequentially. In this report, we give an optimal algorithm for lexicographic sorting that can be used to sort n m-bit keys on an EREW model in Ө (log nlogm) time with Ө (mn) "work". This algorithm is not only as fast as any optimal non-comparison based algorithm, but can also be executed with less work. We also use the proposed algorithm to show that if n Ө (log n) unsigned binary numbers can be sorted optimally on an EREW PRAM than n unsigned binary numbers of unrestricted length can be sorted optimally on an EREW PRAM.
Recommended Citation
Vaidyanathan, Ramachandran; Hartmann, Carlos R.P.; and Varshney, Pramod, "Optimal Parallel Lexicographic Sorting using a Fine-Grained Decomposition" (1991). Electrical Engineering and Computer Science - Technical Reports. 127.
https://surface.syr.edu/eecs_techreports/127
Source
local
Additional Information
School of Computer and Information Science, Syracuse University, SU-CIS-91-01