Idea is very simple. If the array is already sorted, we may exactly know how to get one answer:

first half small numbers would be allocated to odd index numbers and last half would be allocated to even numbers.

My solution is as belows:

```
public void wiggleSort(int[] nums) {
Arrays.sort(nums); // you can use better sorting like quick sort, but best is time O(NlogN)
int[] temp = new int[nums.length];
int s = (nums.length + 1) >> 1, t = nums.length;
for (int i = 0; i < nums.length; i++) {
temp[i] = (i & 1) == 0 ? nums[--s] : nums[--t] ;
}
for (int i = 0; i < nums.length; i++)
nums[i] = temp[i];
}
```