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.