# Wiggle Sort II

Question:

http://www.lintcode.com/en/problem/wiggle-sort-ii/

Given an unsorted array nums, reorder it such that

nums[0] < nums[1] > nums[2] < nums[3]....

Answer:

```
class Solution {
public:
/*
* @param nums: A list of integers
* @return: nothing
*/
inline int partion(vector<int> &nums, int left, int right) {
int pivot = nums[left];
int i = left - 1;
int j = right + 1;
while (1) {
do {
i = i + 1;
} while (nums[i] < pivot);
do {
j = j -1;
} while (nums[j] > pivot);
if (i >= j)
return j;
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
inline void qsort(vector<int> &nums, int left, int right) {
if (left >= right)
return;
int p = partion(nums, left, right);
qsort(nums, left, p);
qsort(nums, p+1, right);
}
void wiggleSort(vector<int> &nums) {
// write your code here
vector<int> temp(nums.size());
qsort(nums, 0, nums.size()-1);
int s = (nums.size() + 1) >> 1;
int t = nums.size();
for (int i = 0; i < nums.size(); i++) {
temp[i] = (i & 1) == 0 ? nums[--s] : nums[--t] ;
}
nums = temp;
}
};
```