# 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 sorted, but I'm not entirely sure.

Could anyone shed some light on this?

• the improvement seems to be justified if the list to be sorted is too long to fit in memory at a time. Carrying out some experiments might help. May 25, 2011 at 16:18
• Take a look at these slides: faculty.cs.byu.edu/~ringger/Winter2006-CS312/lectures/…. May 25, 2011 at 16:45
• The assumption may be that you have a linked list, so to split down the middle requires walking the list once to get its length and then the first half again. May 25, 2011 at 17:32
• To follow up on @Aaron's answer, see en.wikipedia.org/wiki/Batcher_odd-even_mergesort . In normal sequential execution, an even-odd split isn't faster—merging takes Θ(n) time either way—but it can be more easily parallelized. May 27, 2011 at 2:53
• Is it parallelism or caching which makes the even-odd split faster? Jun 26, 2011 at 17:13