Optimal Cost Parallel Algorithms for Lexicographical Ordering
Costas S. Iliopoulos · Purdue e-Pubs (Purdue University System) · 1986
for sorting n integers from the range !!.) algorithm p Optimal cost parallel algorithms for lexicographical ordering on a CREW PRAM are log n presented here.An 0 (I ( ) og nIp {I •...• n} usingp :::;; n processors is given here.Also an algorithm for sorting n strings of size lover an alphabet of size s is presented.that requires 0 ( log n[ ) .!!!.. + !.... ) units of time log (nllp p p and it makes use ofp $ min {nillog I, s /log s } processors.Both algorithms are of oplimal cost withp ::; n X andp ::; min {(n l)1 -:z: • s /log s } for any 0 < x < 1 respectively.