The median filter is one of the basic building blocks in many image processing situations. However, its use has long been hampered by its algorithmic complexity of O (r) in the kernel radius. With the trend toward larger images and proportionally larger filter kernels, the need for a more efficient median filtering algorithm becomes pressing. In this correspondence, a new, simple, yet much faster, algorithm exhibiting O (1) runtime complexity is described and analyzed. It is compared and benchmarked against previous algorithms. Extensions to higher dimensional or higher precision data and an approximation to a circular kernel are presented, as well.