SORTING STRINGS AND CONSTRUCTING DIGITAL SEARCH-TREES IN PARALLEL

We describe two simple optimal-work parallel algorithms for sorting a list L = (X(1),X(2),...,X(m)) of m strings over an arbitrary alphabet Sigma, where Sigma(i=1)(m) \X(i)\ = n and two elements of Sigma can be compared in unit time using a single processor. The first algorithm i s a deterministic algorithm that runs in O(log(2) m/log log m) time an d the second is a randomized algorithm that runs in O(log m) time. Bot h algorithms use O(mlog m + n) operations. Compared to the best-known parallel algorithms for sorting strings, our algorithms offer the foll owing improvements. 1. The total number of operations used by our algo rithms is optimal while all previous parallel algorithms use a nonopti mal number of operations. 2. We make no assumption about the alphabet while the previous algorithms assume that the alphabet is restricted t o {1,2,...,n(0)(1)}. 3. The computation model assumed by our algorithm s is the Common CRCW PRAM unlike the known algorithms that assume the Arbitrary CRCW PRAM. 4. Our algorithms use O(mlogm + n) space, while t he previous parallel algorithms use O(n(1+epsilon)) space, where epsil on is a positive constant. We also present optimal-work parallel algor ithms to construct a digital search tree for a given set of strings an d to search for a string in a sorted list of strings. We use our paral lel sorting algorithms to solve the problem of determining a minimal s tarting point of a circular string with respect to lexicographic order ing, Our solution improves upon the previous best-known result to solv e this problem.