Мы рассмотрим задачу поиска порядковых статистик в потоке и разберем детерминированные алгоритмы. Алгоритм Мунро-Патерсона находит точный ответ, но использует несколько проходов. При разрешенных $p$ проходах алгоритм использует $O(m^{1 \slash p} \log^{2 - 2 \slash p} m \log n)$ памяти.

Статья Мунро-Патерсона (1980)