LC: 280. Wiggle Sort - spiralgo/algorithms GitHub Wiki

280. Wiggle Sort:

The Essence:

A "wiggle sorted" array arr has 2 basic properties:

1. At even indices i, arr[i] ≤ arr[i+1]
2. At odd indices j, arr[j] ≥ arr[j+1]

If an array element does not support these conditions, then it should be switched with the next element. The switch will always leave a correct prefix because of alternating relations.

Details:

The two conditions can be packed up to a single condition, which supports both cases:

if (index is odd) == (arr[i] < arr[i+1]):
    switch with next element