# MPI-I-97-1-012

## On Batcher's Merge Sorts as Parallel Sorting Algorithms

### Rüb, Christine

**MPI-I-97-1-012**. June** **1997, 23 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

In this paper we examine the average running times of Batcher's bitonic

merge and Batcher's odd-even merge when they are used as parallel merging

algorithms. It has been shown previously that the running time of

odd-even merge can be upper bounded by a function of the maximal rank difference

for elements in the two input sequences. Here we give an almost matching lower bound

for odd-even merge as well as a similar upper bound for (a special version

of) bitonic merge.

>From this follows that the average running time of odd-even merge (bitonic

merge) is $\Theta((n/p)(1+\log(1+p^2/n)))$ ($O((n/p)(1+\log(1+p^2/n)))$, resp.)

where $n$ is the size of the input and $p$ is the number of processors used.

Using these results we then show that the average running times of

odd-even merge sort and bitonic merge sort are $O((n/p)(\log n + (\log(1+p^2/n))^2))$,

that is, the two algorithms are optimal on the average if

$n\geq p^2/2^{\sqrt{\log p}}$.

The derived bounds do not allow to compare the two sorting algorithms

program, for various sizes of input and numbers of processors.

Acknowledgement:** **

References to related material:

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

| 246 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/1997-1-012

**BibTeX**
`@TECHREPORT{``Rüb97``,`

` AUTHOR = {R{\"u}b, Christine},`

` TITLE = {On Batcher's Merge Sorts as Parallel Sorting Algorithms},`

` TYPE = {Research Report},`

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

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

` NUMBER = {MPI-I-97-1-012},`

` MONTH = {June},`

` YEAR = {1997},`

` ISSN = {0946-011X},`

`}`