TY - GEN

T1 - Towards optimal parallel radix sorting

AU - Vaidyanathan, R.

AU - Hartmann, C. R.P.

AU - Varshney, P. K.

N1 - Publisher Copyright:
© 1993 IEEE.

PY - 1993

Y1 - 1993

N2 - The authors propose a radix sorting algorithm for n m-bit numbers (where m= Omega (log n) and polynomially upper bounded in n) that runs in O(t(n)log m) time, on any PRAM with mp(n)/logn logm O(logn)-bit processors; p(n) and t(n) are the number of processors and time needed for any deterministic algorithm to sort n logn-bit numbers stably (integer sorting) on the same type of PRAM as used by the radix sorting algorithm. The proposed algorithm has the same factor of inefficiency (if any) as that of the integer sorting algorithm used by it.

AB - The authors propose a radix sorting algorithm for n m-bit numbers (where m= Omega (log n) and polynomially upper bounded in n) that runs in O(t(n)log m) time, on any PRAM with mp(n)/logn logm O(logn)-bit processors; p(n) and t(n) are the number of processors and time needed for any deterministic algorithm to sort n logn-bit numbers stably (integer sorting) on the same type of PRAM as used by the radix sorting algorithm. The proposed algorithm has the same factor of inefficiency (if any) as that of the integer sorting algorithm used by it.

UR - http://www.scopus.com/inward/record.url?scp=0013446102&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0013446102&partnerID=8YFLogxK

U2 - 10.1109/IPPS.1993.262880

DO - 10.1109/IPPS.1993.262880

M3 - Conference contribution

AN - SCOPUS:0013446102

T3 - Proceedings of 7th International Parallel Processing Symposium, IPPS 1993

SP - 193

EP - 197

BT - Proceedings of 7th International Parallel Processing Symposium, IPPS 1993

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 7th International Parallel Processing Symposium, IPPS 1993

Y2 - 13 April 1993 through 16 April 1993

ER -