This one is from leetcode: https://leetcode.com/problems/wiggle-sort-ii/

Given an unsorted array `nums`

, reorder it such that `nums[0] < nums[1] > nums[2] < nums[3]...`

**Example:**

(1) Given `nums = [1, 5, 1, 1, 6, 4]`

, one possible answer is `[1, 4, 1, 5, 1, 6]`

.

(2) Given `nums = [1, 3, 2, 2, 3, 1]`

, one possible answer is `[2, 3, 1, 3, 1, 2]`

.

An old similar problem is wave sort. But in wave sort, it doesn’t has duplicate elements, which we can do it in linear time, O(1) extra space easily. link But for this problem, the difference is that it contains duplicate elements, which make it harder.

Ok, the solution is like below:

1. Sort array in descending order.

2. Put smaller elements into small[].

3. Put larger elements into large[].

4. Merge small[] and large[]: Put small in even position, put large in odd position

For example nums = [1, 2, 3, 4, 5].

Step 1, arr = [5, 4, 3, 2, 1]

Step 2, small = [3, 2, 1]

Step 3, large = [5, 4]

Step 4, arr = [3, 5, 2, 4, 1]

Another example nums = [4, 5, 5, 6]

Step 1, arr = [6, 5, 5, 4]

Step 2, small = [5, 4]

Step 3, large = [6, 5]

Step 4, arr = [5, 6, 5, 4]

check my code on github: link