The median filter is a non-linear filter used for removal of salt and pepper noise from images. Each pixel of the image is replaced by the median of its surrounding elements, the median value is calculated by sorting the data. The complexity of the sorting algorithms used on the median filters are O(n 2) or O(n), depending on the kernel size. Those algorithms were formulated for scalar single processor computers, with few of them successfully adapted and implemented for computer with a parallel architecture. In this paper we present a novel sorting algorithm, with O(n) computational complexity and a highly parallelizable structure, based on the Complementary Cumulative Distribution Function. Furthermore, a 2D median filter based on our proposed sorting algorithm can achieve O(1) complexity. We have implemented our proposed algorithm in two parallel architectures: SIMD Intel and CUDA, which have a throughput of 12.8 and 35 ∼ 57 megapixels per second respectively. © 2012 IEEE.