Merging and Sorting Strings in Parallel

Abstract We show that strings of characters, equipped with the usual lexicographical ordering, can be merged and sorted in parallel as efficiently as integers, although with some loss in speed. Specifically, our main results are: Two sorted lists of strings, containing altogether n characters, can be merged with an optimal time-processor product of O(n) in O (log n ) time on a CRCW PRAM, and in O ((log n ) 2 ) time on an EREW PRAM. Suppose that n integers of size polynomial in n can be sorted in time O(t(n) ) with a time-processor product of O(nf(n)) on a CRCW PRAM, a CREW PRAM or an EREW PRAM, for nondecreasing functions t, f: ℕ → ℕ. Then a list of strings, containing altogether n characters drawn from an alphabet of size polynomial in n, can be sorted in time O(t(n) log n) with a time-processor product of O(n f(n) + n log log n ) on a PRAM of the same type. In particular, such a list can be sorted in O((log n) 2 /log log n ) time with a time-processor product of O ( n log log n ) on a CRCW PRAM.

Authors

• Torben Hagerup
• Ola Petersson

Keywords

No keywords are indexed for this paper.