Permute an array in O(n) time with O(1) extra space with a given ordering function?

Question

This question arises from a problem on a problem solving site (https://practice.geeksforgeeks.org/problems/-rearrange-array-alternately/0).

Given a sorted (ascending order) array $A$ of $N$ numbers, re-arrange the elements of A to be this order: [A[n-1], A[0], A[n-2], A[1], A[n-3], A[2], ...]. While the problem does not actually call for this specific index permutation, that's the approach I took (it will yield the correct answer). If there is a solution that does not involve this approach, I'm interested to see it, but this question specifically is about whether or not it is possible to perform this specific data value re-arrangement without regards to the values stored in the array.

In other words, alternately interleave the maximum, minimum, 2nd-maximum, 2nd-minimum, etc. The algorithm should run in $O(n)$ time and consume only $O(1)$ extra space. It should work regardless of the data values in the array, including scenarios with duplicate values.

Solutions for $O(n^2)$ time with $O(1)$ space and $O(n)$ time with $O(n)$ space are straightforward.

There is a simple function that given a source index in the initial sorted array, determines its destination index in the re-arranged array. I have a partial solution that works by starting at some index and moving through the cycles of source $=>$ destination element moving. But I couldn't find a way to compute the locations of all the separate index-moving cycles. Instead, after completing a cycle, I search the partially re-arranged array for pairs of values that haven't been moved yet (that hold the original, not new, ordering), and use those indices to start a new cycle (this probably means my solution is not $O(n)$ time because of this search). But this doesn't work in general if the elements of the initial array contain duplicate values.

I have an intuition that there must must be an algorithmic move/swap index ordering dependent only on N, but I haven't been able to find one.

Answer 1

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.

Answer 2

Any algorithm which follows the cycles of the permutation will do. They move an element out of the way, place the element that has to take it's place, fill in it's position, until exhausting a cycle; go for the next cycle. Time is $n$ + number of cycles (clearly $O(n)$); extra space is one element worth.