Permute an array in O(n) time with O(1) extra space with a given ordering function?
Reverse the last half of the array in-place and then apply one of the interleaving algorithms mentioned in this question.

That question is for even $n$, and I didn't check whether the answers work for odd $n$ as well. If they don't and it's needed you can do a left rotation to move the middle element to the end (its correct position) and then use one of the even-case algorithms to move the first $n - 1$ elements to their correct positions.