Yeah, those aren't relevant to what I was saying here. Pick any permutation of [2N, 2N + 1, ..., 3N - 1] for N as large as you want and you'll see this algorithm estimate the median as N.
Maybe worth noting that while setting the initial estimate to the first element will help in a lot of cases, it will still fail catastrophically when you happen to get a small element in the beginning, which isn't all that unlikely (say if 1% of your data happens to be zero and the rest similar to before). I haven't researched it but I would imagine actually fixing the algorithm so that it succeeds with high probability in practical (but non-adversarial) cases may well be nontrivial.
