Wave Array Sorting Problem

Your goal is to sort a given unsorted array ARR such that it forms a wave array.

Explanation:

After sorting, the array should satisfy the wave pattern conditions:

• ARR[0] >= ARR[1]
• ARR[1] <= ARR[2]
• ARR[2] >= ARR[3]
• ARR[3] <= ARR[4]
• And so on...

Multiple solutions may exist, but you need to return only one valid wave array.

Example:

Input:

ARR = [4, 3, 5, 2, 3, 1, 2]

Output:

[4, 3, 5, 2, 3, 1, 2]

Explanation:

The array can be arranged in a wave pattern as follows:

• 4 > 3 and 3 < 5
• 5 > 2 and 2 < 3
• 3 > 1 and 1 < 2

Follow-up:

Try to achieve the solution with linear time complexity.

Input:

The input begins with an integer T indicating the number of test cases.
Each of the following 2*T lines specifies one test case:
 - First line: a single integer N, the number of elements in ARR.
 - Second line: N space-separated integers representing ARR.

Output:

For each test case, print the wave array as space-separated integers in a single line.

Constraints:

• 1 <= T <= 50
• 1 <= N <= 10^4
• -10^9 <= ARR[i] <= 10^9

Note:

No need to explicitly print the output. The function implementation will handle it.