[janosett]

I don't know about this particular algorithm, but I believe some similar approaches only converge if you're estimating on values from some stable or slowly changing distribution. A monotonically increasing series would not be a good fit (nor a small dataset).

[mehrdadn]

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.

[janosett]

Fair points, and I agree on the need for a better initial estimate heuristic :-)

[mehrdadn]

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.