324. Wiggle Sort II

It's like merge two lists. But since we are given an array, we have to copy the array, sort it and then merge. Why we start from the end? Let’s see an example [4, 5, 5, 6]. If we start from the beginning, we’ll end up with [4,5,5,6] which is not right. Why? Because the smallest number in the second half is the same as the largest number in the first half and they accidentally meet in the middle. If we start from the end, we’ll guarantee that the largest number in the second half in the middle.

1:  class Solution {  
2:  public:  
3:    void wiggleSort(vector<int>& nums) {  
4:      vector<int> tmp(nums);  
5:      sort(tmp.begin(), tmp.end());  
6:      for (int i = nums.size()-1, j = 0, k = (nums.size()+1)/2; i >= 0; i--) {  
7:        nums[i] = tmp[i & 1 ? k++ : j++];  
8:      }  
9:    }  
10:  };  

I've tried to sort it in place by swapping but realized that there is problem. The merge algorithm above shifts the small number to right however, the swapping will swap the small numbers to end which causes difficulty to find the termination of swapping.

For the follow up question, I have no clue about the virtual indexing algorithm that top rated solution mentions.