Print an Array in Waveform

Problem Rearrange an array into a "wave" so that elements alternate between peaks and valleys: arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] and so on.

Input / Output

• Input: array arr of n numbers, duplicates allowed.
• Output: the array reordered in place into any valid waveform.

Constraints

• Any valid wave arrangement is accepted, so a grader must verify the alternating property rather than compare against one fixed answer.
• In-place preferred, O(1) extra space.
• Duplicates are allowed, since the required relations are >= and <=, not strict.
• Arrays of length 0 or 1 are trivially valid.

Example

• [10,5,6,3,2,20,100,80] → [10,5,6,2,20,3,100,80] is valid; so is the sort-then-swap output [3,2,6,5,20,10,100,80].
• Tricky case: [4,4,4,4] is already valid, because >= and <= both hold between equal neighbours.