public void wiggleSort2(int[] arr) {
        if (arr.length == 0) {
            return;
        }
        int k = arr.length/2;
        KthElementInArray kthElementInArray = new KthElementInArray();
        kthElementInArray.kthElement(arr, k);

        int mid = arr[k];
        int n = arr.length;
        int i = 0, j = 0;
        k = n - 1;
        while (j <= k) {
            if (arr[next(j, n)] > mid) {
                swap(arr, next(i++, n), next(j++, n));
            }
            else if (arr[next(j, n)] < mid) {
                swap(arr, next(j, n), next(k--, n));
            }
            else {
                j++;
            }
        }
    }
Date 03/23/2016
@author Tushar Roy

Convert an unsorted array into an array of form num[0] < num[1] > nums[2] < num[3]....

Time complexity O(n) - This depends on KthElementInArray time
Space complexity O(1)

https://leetcode.com/problems/wiggle-sort/
https://leetcode.com/problems/wiggle-sort-ii/
src/com/interview/array/WiggleSort.java