Given an array of numbers A[N], how do we arrange them in the following order.
A[0] <= A[1] >= A[2] <= A[3]...A[N-1]
For example consider the array A =[6, 9, 36, 24, 42]
The answer can be [6, 36, 9, 42, 24]. There can be multiple answers also like [6, 42, 9, 36, 24]. We have to find out one such answer.
We can solve this problem in a simpler way by sorting the array first. Considering the same example as above
Sorted(A) = [6, 9, 24, 36, 42]
Method1: Start from the second element and swap the elements in pairs
6, 9<-> 24, 36<-> 42 ===> 6, 24, 9, 42, 36
Method2: Interleave the elements of the second half into the first half in reverse order
It becomes 6, 42, 9, 36, 24