Оценка медианы за один проход без сортировки

[nikvic]

Евгений Машеров в сообщении #788936 писал(а):

Но представьте себе, что данные некто (из лучших побуждений!) предварительно отсортировал...

И даже без всяких побуждений. Поступают, например, результаты голосования из разных дистриктов

[vjung]

Есть простой алгоритм, как поддерживать случайную выборку размером N чисел из потока (что-то типа заменять случайный элемент из массива на свежепоступившее число с вероятностью 1/K, где K -- количество всех чисел в потоке).
Дальше можно использовать этот массив из N чисел для оценки медианы. Можно даже вычислить вероятность получить оценочную медиану на n элементов правее или левее настоящей.

[Евгений Машеров]

Можно. Но отклонение будет достаточно велико.