Efficient Median Algorithm With Very Constrained Operators

Question

What is the most efficient algorithm for finding the median of an array when the available operations are limited to Max(), Min(), Multiply, Add, and no conditionals are allowed. Pivots and sorts are not allowed. The algorithm I have come up with so far seems very inefficient and goes like so:

1. For an array of length n, create a working array of length 2n by doing pairwise Max() comparisons for every pair of elements in the input array. This 2n array is guaranteed not to contain the lowest value from the original (or one fewer of the lowest value if there were ties for the lowest value)
2. Recursively call (1) n/2 times
3. Take min() of final array

There's got to be a faster algorithm!

Answer 1

I can get you an improvement for the first step; every time you do that first step, you're basically trying to find the minimum, and then continue on the rest of the array. You don't need to do all that just to find the minimum; instead of making that large array (which sounds like it contains $\binom n 2$ elements, not 2ドルn,ドル unless I misunderstood you), you can basically do the following:

Starting from the left, take every pair of consecutive elements, and put the minimum of the two on the right. Something like this in pseudocode:

temp1 = min(array[i], array[i+1])
temp2 = max(array[i], array[i+1])
array[i] = temp2
array[i+1] = temp1

What will happen is that the minimum element gets moved all the way to the far right using 2ドル(n-1)$ mins and maxs. We can then do our recursive call on the first $n-1$ elements, and repeat until we finally pull out the median.¹

---

^{1 Some of you reading this will note that basically what we end up with is a bubble sort (reverse in the example I gave) where we stop as soon as we figure out the median. If you decide to move the max to the right instead, then we pretty much are doing a normal bubble sort, but stopping once we get the median.}

• Michael Mullany: That's a big improvement thanks! (and yes that should n c 2, not 2n)
• Michael Mullany: btw, the practical effect of this is to enable me to do a median filter using SVG filter primitives: codepen.io/mullany/pen/dmbvz. Thanks!!!