Definitions:

y[1],y[2],...,y[n] is sorted
if y[1] <= y[2] <= ... <= y[n].

odd(x[1],x[2],...,x[n]) = (y[1],y[2],...,y[n]) means that
y[1] = min{x[1],x[2]}, y[3] = min{x[3],x[4]}, etc.;
y[2] = max{x[1],x[2]}, y[4] = max{x[3],x[4]}, etc.; and
y[n] = x[n] if n is odd.

even(x[1],x[2],...,x[n]) = (y[1],y[2],...,y[n]) means that
y[1] = x[1];
y[2] = min{x[2],x[3]}, y[4] = min{x[4],x[5]}, etc.;
y[3] = max{x[2],x[3]}, y[5] = max{x[4],x[5]}, etc.; and
y[n] = x[n] if n is even.

oddeven_k(x) means
x if k = 0;
odd(oddeven_(k-1)(x)) if k is odd;
even(oddeven_(k-1)(x)) otherwise.


Problem: Prove that oddeven_n(x[1],...,x[n-1],1) is sorted
if oddeven_(n-1)(x[1],...,x[n-1]) is sorted and all x[k]'s are in {0,1}.