# MPI-I-93-152

## Optimal parallel string algorithms: sorting, merching and computing the minimum

### Hagerup, Torben

#### 1993, 25 pages.

.

##### Status: available - back from printing

We study fundamental comparison problems on
strings of characters, equipped with the usual
lexicographical ordering.
For each problem studied, we give a parallel algorithm
that is optimal with respect to at least one
criterion for which no optimal
algorithm was previously known.
Specifically, our main results are:
%
\begin{itemize}
\item Two sorted sequences of strings, containing
altogether $n$~characters, can be merged in
$O(\log n)$ time using $O(n)$ operations
on an EREW PRAM.
This is optimal as regards both the running time
and the number of operations.
\item A sequence of strings, containing altogether
$n$~characters represented by integers of size
polynomial in~$n$, can be sorted
in $O({{\log n}/{\log\log n}})$ time
using $O(n\log\log n)$ operations on
a CRCW PRAM.
The running time is optimal for any
polynomial number of processors.
\item The minimum string in a sequence of strings
containing altogether $n$ characters can be
found using (expected) $O(n)$ operations in
constant expected time on a randomized
CRCW PRAM, in $O(\log\log n)$ time on a
deterministic CRCW PRAM with a program depending on~$n$,
in $O((\log\log n)^3)$ time on a
deterministic CRCW PRAM with a program
not depending on~$n$,
in $O(\log n)$ expected time on a randomized
EREW PRAM, and in $O(\log n\log\log n)$ time
on a deterministic EREW PRAM.
The number of operations is optimal, and
the running time is optimal for the randomized algorithms
and, if the number of processors is limited to~$n$,
for the nonuniform deterministic CRCW
PRAM algorithm as wel

**URL to this document: **https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-152

**BibTeX**
`@TECHREPORT{``Hagerup93``,`

` AUTHOR = {Hagerup, Torben},`

` TITLE = {Optimal parallel string algorithms: sorting, merching and computing the minimum},`

` TYPE = {Research Report},`

` INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},`

` ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},`

` NUMBER = {MPI-I-93-152},`

` YEAR = {1993},`

` ISSN = {0946-011X},`

`}`