Base case: only one element is processed, no constraints are violated.
Step: if i % 2 == 0: If we do not swap anything at this step, the prefix remains valid. Otherwise, we have the following situation: a[i - 2] >= a[i - 1] > a[i]. When we make a swap, we can see that the constraints are not violated for the i - 2 and i - 1 elements, and the last position is fixed. For an odd i, the situation is similar.
I hope this would help you:
Making [even, odd] pairs to be [small, large] will ensure the number before the odd index will be smaller than itself.
Making [odd, even] pairs to be [large, small] will ensure the number after the odd index will be larger than itself.
How to prove?
Assume we have the following sequence after finishing the first round of exchange:
[a1, a, b1, b, c1, c] here a1<a, b1<b, c1<c and this is guaranteed by the first switch.
So, here we need to do the second switch for pairs [odd, even],
Starting from [a, b1],
if a>b1, we do not need to switch the element, continue to the next [odd, even] pair.
if a<b1, we did the switch and make it become:
[a1, b1, a, b, c1, c]
here because a1<a, a<b1, so a1<b1. so we have a1<b1>a.
And so forth.
My code did need O(n) space, yes. Apparently I didn't save it, but it was something like this:
m = median(nums)
ordered = [x for x in nums if x<m] + [m]*nums.count(m) + [x for x in nums if x>m]
half = (len(nums) + 1) / 2
nums[::2], nums[1::2] = ordered[:half], ordered[half:]
I guess it can be done in-place, think of (unstable) partitioning just with unusual indexing. Not like usual to indexes 0,1,2,3,4,5 but directly to indexes 0,2,4,1,3,5 (evens followed by odds). No idea how nice/ugly it would be. I probably won't try it before it's published :-)