I spent a lot of time looking for an in-place linear algorithm for finding the median. Thanks to @StefanPochmann for posting a link to Stack Overflow, I found this one. It's really esoteric, and what's worse, it's not really a complete algorithm because at some point it just says

then, using any other linear-time in-place selection algorithm, search

the sample for two elements x,y, of ranks...

So in the end, it's not exactly an algorithm for linear in-place selection, but rather an algorithm for finding the best sample for other algorithms to optimize the total number of operations involved. The paper provides references to other algorithms, but I've been unable to find any of them in the open. But surely, one could buy some books or access to some scientific site, and in the end it is possible to solve this in linear time and constant space. The code would be a real mess, though, and I'm not even sure if it will fit within the code length limit.

But there is a better way. Once I saw that I was amazed how absurdly simple it is. Made me feel like Dr. Watson after another explanation by Holmes.

Indeed, why bother with all those algorithms if we know that possible values of the median lie between `INT_MIN`

and `INT_MAX`

. We can use binary search on the entire range! And since checking whether some number is the median or not takes O(n), then the whole thing is just O(n log 2^32). But log 2^32 is a constant, so it's technically still O(n).

```
public void wiggleSort(int[] nums) {
if (nums.length <= 1) {
return;
}
int p = bsSelect(nums, (nums.length - 1) / 2 + 1);
// Reverse Dutch National Flag with Wiggle Indexing (StefanPochmann's Virtual Indexing).
// Thanks to apolloydy for reversing this thing.
final int n = nums.length;
int m = 0, r = nums.length - 1;
int lw = 1, mw = 1, rw = (1 + 2 * (nums.length - 1)) % (n | 1);
while (m <= r) {
if (nums[mw] > p) {
int tmp = nums[mw];
nums[mw] = nums[lw];
nums[lw] = tmp;
mw = (mw + 2) % (n | 1);
++m;
lw = (lw + 2) % (n | 1);
} else if (nums[mw] < p) {
int tmp = nums[mw];
nums[mw] = nums[rw];
nums[rw] = tmp;
rw = (rw - 2 + (n | 1)) % (n | 1);
--r;
} else {
mw = (mw + 2) % (n | 1);
++m;
}
}
}
private int bsSelect(int[] nums, int k) {
if (k < 1 || k > nums.length) {
throw new IllegalArgumentException("length=" + nums.length + " k=" + k);
}
int left = Integer.MIN_VALUE, right = Integer.MAX_VALUE;
while (left <= right) {
int mid = (left < 0 && right > 0) ? (left + right) / 2 : left + (right - left) / 2;
int cl = 0, cg = 0, d = 0;
for (int n : nums) {
if (n < mid) {
if (++cl > k - 1) {
d = +1; // mid larger than kth
break;
}
} else if (n > mid) {
if (++cg > (nums.length - k)) {
d = -1; // mid smaller than kth
break;
}
}
}
if (d == 0) {
return mid;
} else if (d < 0) {
left = mid + 1;
} else {
right = mid - 1;
}
}
throw new AssertionError();
}
```

It almost feels like cheating. But according to that post on Quora, that's exactly what the interviewers expect. Thinking out of the box and such.

This thing runs on my PC for 500 million elements in 31 seconds if the array is sorted and in 38 seconds if it's wiggle-sorted to begin with. This is slower than the median of medians solution (22 and 12 seconds), but this time it's true O(1) space.

**Note** that I moved the argument check to the beginning because the old variant was really bugged. And I fixed the binary search because I forgot to do the `mid + 1`

/ `mid - 1`

part. That turned 15 ms into 18 ms for some reason, and if I put `while (true)`

there then it raises the runtime to 20 ms. Figures. But at least it's not bugged now (I hope). Note that integer overflows aren't possible because if mid is either `INT_MIN`

or `INT_MAX`

then the respective condition for decreasing/increasing it would be false.

As noted in the comment below, `mid = (left + right) / 2`

may overflow, so it was replaced by that ugly, but overflow-aware line.