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, A[n-2], A, A[n-3], A, ...]. 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.