# Wiggle Sort

Moderate
0/80
Contributed by

## Problem statement

You are given an array ‘ARR’ containing ‘N’ integers, you need to sort the array such that a wiggle sequence is formed. A wiggle sequence satisfies the following property: ARR[0] ≤ ARR[1] ≥ ARR[2] ≤ ARR[3] ≥ ARR[4] ≤ ARR[5] …..

If there are multiple answers, you may print any of them.

``````Can you try to solve this problem in O(N) time without using extra space?
``````
Custom Input :
``````Kindly use print statements to debug the code and print array.
``````
Example :
``````If ‘N’ = 5 and ‘ARR’ = { 1, 2, 3, 4, 5 }

Then rearranging the input array to { 1, 4, 2, 5, 3 } create a wiggle sequence.

Other rearrangements like { 2, 4, 3, 5, 1 }, { 3, 5, 1, 4, 2} are also considered correct.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints :
``````1 ≤ T ≤ 10
1 ≤ N ≤ 5000
-10^9 ≤ ARR[i] ≤ 10^9

Time limit: 1 sec
``````
##### Sample Input 1 :
``````2
5
1 2 3 4 5
4
1 3 2 2
``````
##### Sample Output 1 :
``````1 4 2 5 3
1 3 2 2
``````
##### Explanation For Sample Input 1 :
``````For test case 1 :
We will print {1, 4, 2, 5, 3} as it is a valid rearrangement of the input array and is a wiggle sequence.

For test case 2 :
The input array is itself a wiggle sequence, so we can directly return it.
``````
##### Sample Input 2 :
``````2
5
1 1 1 1 1
2
1 2
``````
##### Sample Output 2 :
``````1 1 1 1 1
1 2
``````
Console