Efficient Median Algorithm With Very Constrained Operators
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 $2n$, 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



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.