On the Average Running Time of Odd–Even Merge Sort

✍ Scribed by Christine Rüb

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 178 KB
• Volume: 22
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1996.0812

✦ Synopsis

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 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 . Ž Ž. Ž Ž 2 ... of length n each can be implemented to run in time O nrp log 2 q p rn on the average, 1 and that odd᎐even merge sort can be implemented to run in time ŽŽ .Ž Ž 2 ... O nrp log n q log p log 2 q p rn on the average. In the case of merging Ž . Ž sorting , the average is taken over all possible outcomes of the merge 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 G p 2 . The constants involved are also quite small. ᮊ 1997 Academic Press 2 .. ⌰ nrp log nrp q log p , where p is the number of processors used.