Look at jallmanns comment [0]. Quickselect partially sorts the input array. If y...

andrewcooke · on May 18, 2013

even w ordered data, sorting is O(n) isn't it?

sp332 · on May 18, 2013

Ordered data? Lookups into sorted data can use a binary search and are only O(log n).

andrewcooke · on May 18, 2013

but you need to move n/2 to "make room" - think of the whole process.

edit: you're not wrong, but what i am saying is that to make the filter practical you have to save the new point, too.

sorry for brief comments. on vacn w tablet only.