Thanks for the link. Note, though, that the median algorithm used there uses a different parameter for n than OP. It also is bucketsort-based and O(n), O(1) only amortized (in both parameters).
Additional knowledge of your data is often useful, like using the fact that all data are 8-bit integers above. Similarly, if you know your data is uniformly distributed, you could try Torben (in TFA) for pivot selection in quickselect.
Comments
If the window is the length of the data, that becomes O(n log n) -- essentially no better than a sort?
For images and other kernel-based filtering, there is a O(1) median algorithm available: http://nomis80.org/ctmf.html
Thanks for the link. Note, though, that the median algorithm used there uses a different parameter for n than OP. It also is bucketsort-based and O(n), O(1) only amortized (in both parameters).
Additional knowledge of your data is often useful, like using the fact that all data are 8-bit integers above. Similarly, if you know your data is uniformly distributed, you could try Torben (in TFA) for pivot selection in quickselect.
maybe i have misunderstood the application - i am talking about "median smoothing" with a "running window". w is typically fixed.
but thanks for link to paper - that is new to me.