This post is mainly about what I call "virtual indexing" technique (I'm sure I'm not the first who came up with this, but I couldn't find anything about it, so I made up a name as well. If you know better, let me know).

## Solution

```
void wiggleSort(vector<int>& nums) {
int n = nums.size();
// Find a median.
auto midptr = nums.begin() + n / 2;
nth_element(nums.begin(), midptr, nums.end());
int mid = *midptr;
// Index-rewiring.
#define A(i) nums[(1+2*(i)) % (n|1)]
// 3-way-partition-to-wiggly in O(n) time with O(1) space.
int i = 0, j = 0, k = n - 1;
while (j <= k) {
if (A(j) > mid)
swap(A(i++), A(j++));
else if (A(j) < mid)
swap(A(j), A(k--));
else
j++;
}
}
```

## Explanation

First I find a median using `nth_element`

. That only guarantees O(n) **average** time complexity and I don't know about space complexity. I might write this myself using O(n) time and O(1) space, but that's not what I want to show here.

This post is about what comes **after** that. We can use three-way partitioning to arrange the numbers so that those *larger than* the median come first, then those *equal to* the median come next, and then those *smaller than* the median come last.

Ordinarily, you'd then use one more phase to bring the numbers to their final positions to reach the overall wiggle-property. But I don't know a nice O(1) space way for this. Instead, I embed this right into the partitioning algorithm. That algorithm simply works with indexes 0 to n-1 as usual, but sneaky as I am, I rewire those indexes where I want the numbers to actually end up. The partitioning-algorithm doesn't even know that I'm doing that, it just works like normal (it just uses `A(x)`

instead of `nums[x]`

).

Let's say `nums`

is `[10,11,...,19]`

. Then after nth_element and ordinary partitioning, we might have this (15 is my median):

```
index: 0 1 2 3 4 5 6 7 8 9
number: 18 17 19 16 15 11 14 10 13 12
```

I rewire it so that the first spot has index 5, the second spot has index 0, etc, so that I might get this instead:

```
index: 5 0 6 1 7 2 8 3 9 4
number: 11 18 14 17 10 19 13 16 12 15
```

And 11 18 14 17 10 19 13 16 12 15 is perfectly wiggly. And the whole partitioning-to-wiggly-arrangement (everything after finding the median) only takes O(n) time and O(1) space.

If the above description is unclear, maybe this explicit listing helps:

Accessing `A(0)`

actually accesses `nums[1]`

.

Accessing `A(1)`

actually accesses `nums[3]`

.

Accessing `A(2)`

actually accesses `nums[5]`

.

Accessing `A(3)`

actually accesses `nums[7]`

.

Accessing `A(4)`

actually accesses `nums[9]`

.

Accessing `A(5)`

actually accesses `nums[0]`

.

Accessing `A(6)`

actually accesses `nums[2]`

.

Accessing `A(7)`

actually accesses `nums[4]`

.

Accessing `A(8)`

actually accesses `nums[6]`

.

Accessing `A(9)`

actually accesses `nums[8]`

.

Props to apolloydy's solution, I knew the partitioning algorithm already but I didn't know the name. And apolloydy's idea to partition to reverse order happened to make the index rewiring simpler.