In this talk I will show that the following problems are equivalent,
both in theory and in practice:
(1) median filtering: given an n-element vector, compute the sliding
window median with window size k,
(2) piecewise sorting: given an n-element vector, divide it in n/k
blocks of length k and sort each block.
By prior work, median filtering is known to be at least as hard as
piecewise sorting: with a single median filter operation we can sort
θ(n/k) blocks of length θ(k). Our recent work shows that median
filtering is also as easy as piecewise sorting: we can do median
filtering with one piecewise sorting operation and linear-time
postprocessing; moreover, the algorithm is very efficient in practice.
See
http://arxiv.org/abs/1406.1717 for more information.