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:

	object PartnerOddEven {
	/**
	*
	* Calculates partner in Batcher Odd-Even network.
	*
	* @param n node index: 0, 1, 2, 3, ... 2^d^-1
	* @param l merge stage: 1, 2, 3, ... d
	* @param p stage step: 1, 2, 3, ... l
	* @return Returns partner node, or self (n) if no partner for this step
	*/
	def partner(n: Int, l: Int, p: Int): Int = {
	assert(p <= l, "p should be at most l")
	assert(p > 0, "p should be at least 1")
	assert(l > 0, "l should be at least 1")
	if (p == 1)
	n ^ (1 << (l - 1))
	else {
	val (scale, box) = (1 << (l - p), 1 << p)
	val sn = n / scale - (n / scale / box) * box
	if (sn == 0 || sn == box - 1) n
	else if (sn % 2 == 0) n - scale else n + scale
	}
	}
	}

view raw OddEvenMerge.scala hosted with ❤ by GitHub

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.