324. Wiggle Sort II

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        n = nums.size();
        int mid = findM(nums);
        cout<<mid<<"mid"<<endl;
        semisort(nums, mid);
        for (int i = 0; i < n; i++)
            cout<<i<<' '<<cvtIdx(i)<<endl;
        return;
    }
private:
    int n;
    int findM(vector<int>& nums) {
        int tar = (nums.size() + 1) / 2;
cout<<tar<<"tar"<<endl;
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int i = l, j = r, x = nums[i];
            while (i < j) {
                while (i < j && nums[j] >= x) j--;
                if (i < j) nums[i++] = nums[j];
                while (i < j && nums[i] <= x) i++;
                if (i < j) nums[j--] = nums[i];
            }
            nums[i] = x;
            if (i == tar) return x;
            if (i < tar) l = i + 1;
                else r = i - 1;
        }
        return nums[tar];
    }

    void semisort(vector<int>& nums, int mid) {
        int l = 0, r = nums.size() - 1;
        for (int k = l; k <= r; k++)
            if (nums[cvtIdx(k)] > mid && k != l)
                swap(nums[cvtIdx(k--)], nums[cvtIdx(l++)]);
                else if (nums[cvtIdx(k)] < mid && k != r)
                    swap(nums[cvtIdx(k--)], nums[cvtIdx(r--)]);
    }



    int cvtIdx(int x) {
        //return x;
        // if (x == 4) return 0;
        // if (x == 0) return 1;
        // if (x == 5) return 2;
        // if (x == 1) return 3;
        // if (x == 6) return 4;
        // if (x == 2) return 5;
        // if (x == 7) return 6;
        // if (x == 3) return 7;
        // if (x == 8) return 8;
        return (2 * x + 1) % (n | 1);
        if (x >= (n + 1) / 2)
            return (x - (n + 1) / 2) * 2 + 1;
        return x * 2;
    }
};