• DocumentCode
    3486793
  • Title

    Towards optimal parallel radix sorting

  • Author

    Vaidyanathan, R. ; Hartmann, C.R.P. ; Varshney, P.K.

  • Author_Institution
    Dept. of Electr. & Comput. Eng., Louisiana State Univ., Baton Rouge, LA, USA
  • fYear
    1993
  • fDate
    13-16 Apr 1993
  • Firstpage
    193
  • Lastpage
    197
  • Abstract
    The authors propose a radix sorting algorithm for n m -bit numbers (where m=Ω(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
  • Keywords
    computational complexity; data structures; parallel algorithms; random-access storage; sorting; PRAM; deterministic algorithm; integer sorting; optimal parallel radix sorting; polynomially upper bounded; Atomic measurements; Contracts; Parallel algorithms; Partitioning algorithms; Phase change random access memory; Polynomials; Sorting;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Parallel Processing Symposium, 1993., Proceedings of Seventh International
  • Conference_Location
    Newport, CA
  • Print_ISBN
    0-8186-3442-1
  • Type

    conf

  • DOI
    10.1109/IPPS.1993.262880
  • Filename
    262880
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3486793