On the Average Running Time of Odd–Even Merge Sort |
| |
Authors: | Christine Rüb |
| |
Institution: | Max-Planck-Institut für Informatik Im Stadtwald, D-66123, Saarbrücken, Germany |
| |
Abstract: | This paper gives an upper bound for the average running time of Batcher's odd–even merge sort when implemented on a collection of processors. We consider the case wheren, the size of the input, is an arbitrary multiple of the numberpof processors used. We show that Batcher's odd–even merge (for two sorted lists of lengthneach) can be implemented to run in timeO((n/p)(log(2 + p2/n))) on the average,1and that odd–even merge sort can be implemented to run in timeO((n/p)(log n + log p log(2 + p2/n))) on the average. In the case of merging (sorting), the average is taken over all possible outcomes of the merge (all possible permutations ofnelements). That means that odd–even merge and odd–even merge sort have an optimal average running time ifn ≥ p2. The constants involved are also quite small. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|