@article {15025,
title = {Sorting strings and constructing digital search trees in parallel},
journal = {Theoretical Computer Science},
volume = {154},
year = {1996},
month = {1996/02/05/},
pages = {225 - 245},
abstract = {We describe two simple optimal-work parallel algorithms for sorting a list L= (X1, X2, {\textellipsis}, Xm) of m strings over an arbitrary alphabet Σ, where ∑i = 1m{\textbrokenbar}Xi{\textbrokenbar} = n and two elements of Σ can be compared in unit time using a single processor. The first algorithm is a deterministic algorithm that runs in O(log2m/log log m) time and the second is a randomized algorithm that runs in O(logm) time. Both algorithms use O(m log m + n) operations. Compared to the best-known parallel algorithms for sorting strings, our algorithms offer the following improvements. 1.1. The total number of operations used by our algorithms is optimal while all previous parallel algorithms use a nonoptimal number of operations.
2.
2. We make no assumption about the alphabet while the previous algorithms assume that the alphabet is restricted to {1, 2, {\textellipsis}, no(1)}.
3.
3. The computation model assumed by our algorithms is the Common CRCW PRAM unlike the known algorithms that assume the Arbitrary CRCW PRAM.
4.
4. Our algorithms use O(m log m + n) space, while the previous parallel algorithms use O(n1 + ε) space, where ε is a positive constant.
We also present optimal-work parallel algorithms to construct a digital search tree for a given set of strings and to search for a string in a sorted list of strings. We use our parallel sorting algorithms to solve the problem of determining a minimal starting point of a circular string with respect to lexicographic ordering. Our solution improves upon the previous best-known result to solve this problem.
},
isbn = {0304-3975},
doi = {10.1016/0304-3975(94)00263-0},
url = {http://www.sciencedirect.com/science/article/pii/0304397594002630},
author = {JaJa, Joseph F. and Ryu,Kwan Woo and Vishkin, Uzi}
}