Если заранее известен набор значений элементов массива (0..255), а количество элементов сильно больше набора значений (несколько тысяч), можно использовать гистограмму — считать количество элементов каждого значения (5 нулей, 340 единиц, 210 двоек… ) В гистограмме середину найти значительно проще (будет известно общее количество, достаточно суммировать количества в ячейках до превышения половины от общего числа. Элемент, на котором будет достигнута середина и будет медианой)
Данный подход очень сильно ускоряет медианную фильтрацию изображений с большим радиусом (обновление гистограммы можно нехило оптимизировать, обновляя лишь «края» при переходе к соседнему пикселю)
