English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

On the average running time of odd-even merge sort

MPS-Authors
/persons/resource/persons45318

Rüb,  Christine
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

MPI-I-95-1-010.pdf
(Any fulltext), 9MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Rüb, C.(1995). On the average running time of odd-even merge sort (MPI-I-1995-1-010). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B6D4-5
Abstract
This paper is concerned with the average running time of Batcher's odd-even merge sort when implemented on a collection of processors. We consider the case where $n$, the size of the input, is an arbitrary multiple of the number $p$ of processors used. We show that Batcher's odd-even merge (for two sorted lists of length $n$ each) can be implemented to run in time $O((n/p)(\log (2+p^2/n)))$ on the average, and that odd-even merge sort can be implemented to run in time $O((n/p)(\log n+\log p\log (2+p^2/n)))$ on the average. In the case of merging (sorting), the average is taken over all possible outcomes of the merging (all possible permutations of $n$ elements). That means that odd-even merge and odd-even merge sort have an optimal average running time if $n\geq p^2$. The constants involved are also quite small.