Another way ..
Taking first index as 1
At odd positions, put elements in ascending order
And at even positions, put elements in descending order.
For Example,
Consider array : 1 2 3 4 5 6 7 8
Unsorted : 1 8 2 7 3 6 4 5
As there are n moves, O(n) Complexity