# MPI-I-93-152

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

### Hagerup, Torben

**MPI-I-93-152**. ** **1993, 25 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

MPI-I-93-152.pdf | 14191 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://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},`

`}`