Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why is an even-odd split 'faster' for MergeSort?

MergeSort is a divide-and-conquer algorithm that divides the input into several parts and solves the parts recursively.

...There are several approaches for the split function. One way is to split down the middle. That approach has some nice properties, however, we'll focus on a method that's a little bit faster: even-odd split. The idea is to put every even-position element in one list, and every odd-position in another.

This is straight from my lecture notes. Why exactly is it the case that the even-odd split is faster than down the middle of the array?

I'm speculating it has something to do with the list being passed into MergeSort and having the quality of already already sorted, but I'm not entirely sure.

Could anyone shed some light on this?

Edit: I tried running the following in Python...

global K
K = []
for i in range (1, 100000):
    K.append(i)


def testMergeSort():
"""
testMergeSort shows the proper functionality for the
Merge Sort Algorithm implemented above.
"""

t = Timer("mergeSort([K])", "from __main__ import *")
print(t.timeit(1000000))

p = Timer("mergeSort2([K])", "from __main__ import *")
print(p.timeit(1000000))

(MergeSort is the even-odd MergeSort, MergeSort2 divides down the center)

And the result was:

0.771506746608

0.843161219237

like image 807
Unsure Avatar asked May 25 '11 12:05

Unsure


1 Answers

I can see that it could be possible that it is better because splitting it with alternative elements means you don't have to know how long the input is to start with - you just take elements and put them in alternating lists until you run out.

Also you could potentially starting splitting the resulting lists before you have finished iterating through the first list if you are careful allowing for better parallel processing.

I should add that I'm no expert on these matters, they are just things that came to mind...

like image 86
Chris Avatar answered Sep 22 '22 18:09

Chris