Sorting strings and constructing digital search trees in parallel

We describe two simple optimal-work parallel algorithms for sorting a list L= (X1, X2, …, Xm) of m strings over an arbitrary alphabet Σ, where ∑i = 1m¦Xi¦ = 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, …, 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.