Nice problem via some Microsoft blog (can't remember which):
You are given an array with an even number N of integers. Suffle the array according to the rule A[i] = a[(i%2)(N/2) + i/2], where a[i] and A[i] are the values of the i-th location before and after the shuffle (zero-based index). Do it in O(N logN) time and O(1) space.
[0, 1, 2, 3, 4, 5]
[0, 3, 1, 4, 2, 5]
NOTE: you do not know anything about the values in the array (i.e. 0, 1, 2,... are specific to this example)