Document Type

Report

Date

1-1991

Embargo Period

5-2-2012

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.

Additional Information

School of Computer and Information Science, Syracuse University, SU-CIS-91-01

Source

local

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.