Thursday, May 7, 2015

Batcher's odd-even merging network

Batcher's odd-even merge based sorting network node partner calculation.

I couldn't find a closed-form formula for odd-even network node partner calculation. The only available implementations were recursive and not very elegant. Here is the code that was provided on Wikipedia.

So I decided to work out a simpler and more intuitive solution to odd-even merge-based sorting network partner calculation, and here it is:

Also, here I put up a little interactive sorting network generator. Of course, I updated that Wikipedia article, to make it easier for learners :)

Here is the best performance analysis of this network that I could find.

No comments: