Prompt: Given a list of integers, [a₀ , a₁ , a₂ , … , a_n ], we want to sort the list such that it satisfies a₀ < a₁ > a₂ < a₃ > a₄ < … , a_n .

Example:

Input: nums = [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: [1,4,1,5,1,6] is also accepted.

Input: nums = [1,3,2,2,3,1]
Output: [2,3,1,3,1,2]

Solution: To solve this problem, we need to realize that there are two groups of integers, peaks and dips. The peaks are all the integers that are greater than their neighbors and dips are all the integers that are less than their neighbors. We also want to emphasize that all peaks are greater than all dips and all dips are less than peaks.

Note: dips < peaks

In order to get all the peak and dip integers, we can sort the list and split it in half. The first half would be the dips and the second half would be the peaks. It satisfies the condition, dips < peaks.

Now that we have all the peaks and dips, we can layer the peaks and dips in an alternating fashion, [dip, peak, dip, peak, dip, … ]. We can see that it satisfies the wiggle sort condition: dip < peak > dip < peak > dip …