<p>Looking at the <a href="http://en.wikipedia.org/wiki/Batcher_odd-even_mergesort" rel="nofollow">graphing network on Wikipedia</a> and <a href="http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/networks/oemen.htm" rel="nofollow">this page</a> for even-odd merge sort it appears that it has a higher complexity than traditional merge-sort. However, at the cost of more operations, notice how the operations remain independent of one another.</p>

<p>That is to say, where as in merge sort you eventually end up merging 4 lists and then 2 lists, which cannot be done in parallel, even-odd merge sort allows you to operate in parallel until the end of the algorithm.</p>

<p>The Wikipedia article also points out that it is reasonably fast for doing sort in graphics hardware. I suspect this is because where as merge sort your inputs to compare-and-swap depend on which previous element was merged, the inputs to compare-and-swap in even-odd-merge-sort are <em>always</em> the same.</p>

<p>Hope that helps! </p>

CC BY-SA 3.0
2011-05-27T13:29:52.123Z
2011-05-27T14:51:09.187Z
2011-05-27T14:51:09.187Z
Sam
<blockquote>
<p>MergeSort is a divide-and-conquer algorithm that divides the input into several parts and solves the parts recursively.</p>
<p>...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.</p>
</blockquote>
<p>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?</p>
<p>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.</p>
<p>Could anyone shed some light on this?</p>

CC BY-SA 3.0
2011-05-25T16:18:16.753Z
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.
singhsumit
CC BY-SA 3.0
2011-05-25T16:45:06.763Z
Take a look at these slides: http://faculty.cs.byu.edu/~ringger/Winter2006-CS312/lectures/lecture39-parallelmergesort.pdf.
Aaron Sterling
CC BY-SA 3.0
2011-05-25T17:32:38.053Z
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.
Peter Taylor
CC BY-SA 3.0
2011-05-27T02:53:42.077Z
To follow up on @Aaron's answer, see http://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.
Jeffε
CC BY-SA 3.0
2011-06-26T17:13:08.623Z
Is it parallelism or caching which makes the even-odd split faster?
Peter Shor 
CC BY-SA 3.0
2011-06-26T21:44:33.850Z
@Peter Shor: My naive answer is parallelism, because the notion is to assign a separate processor to sort each sublist created.  Standard mergesort can't be farmed out this way.  I wouldn't be surprised if there were a caching issue in real life, but I don't yet see how it relates here.
Aaron Sterling
<ds.algorithms><sorting>
Why is an even-odd split 'faster' for MergeSort?
Unsure
# Why is an even-odd split 'faster' for MergeSort?

(Asked by: username_0 on 2011-05-25)

> 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?

**Tags:** ds.algorithms, sorting

> **Comments:**
> **username_1**: 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.  
> **username_2**: Take a look at these slides: http://faculty.cs.byu.edu/~ringger/Winter2006-CS312/lectures/lecture39-parallelmergesort.pdf.  
> **username_3**: 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.  
> **username_4**: To follow up on @Aaron's answer, see http://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.  
> **username_5**: Is it parallelism or caching which makes the even-odd split faster?  
> **username_2**: @Peter Shor: My naive answer is parallelism, because the notion is to assign a separate processor to sort each sublist created.  Standard mergesort can't be farmed out this way.  I wouldn't be surprised if there were a caching issue in real life, but I don't yet see how it relates here.  

---

## 1 answers

### Answer by username_6 on 2011-05-27. Score: 2

Looking at the [graphing network on Wikipedia](http://en.wikipedia.org/wiki/Batcher_odd-even_mergesort) and [this page](http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/networks/oemen.htm) for even-odd merge sort it appears that it has a higher complexity than traditional merge-sort. However, at the cost of more operations, notice how the operations remain independent of one another.

That is to say, where as in merge sort you eventually end up merging 4 lists and then 2 lists, which cannot be done in parallel, even-odd merge sort allows you to operate in parallel until the end of the algorithm.

The Wikipedia article also points out that it is reasonably fast for doing sort in graphics hardware. I suspect this is because where as merge sort your inputs to compare-and-swap depend on which previous element was merged, the inputs to compare-and-swap in even-odd-merge-sort are *always* the same.

Hope that helps!


---

