Изменения

Выбор <tex>s</tex>-ого наибольшего числа среди <tex>n</tex> чисел , упакованных в <tex>n/g</tex> контейнеров , может быть сделана сделан за время <tex>O(n \log g/g)</tex> время и с использованием <tex>O(n/g)</tex> местапамяти. Конкретно медиана В том числе, так может быть так найденамедиана.

Так как возможно делать попарное сравнение <tex>g</tex> чисел в одном контейнере с <tex>g</tex> числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, возможно упаковать медианы из первого, второго, <tex>\ldots</tex>, <tex>g</tex>-ого чисел из 5 контейнеров в один контейнер за константное время. Таким образом, набор <tex>S</tex> из медиан теперь содержится в <tex>n/(5g)</tex> контейнерах. Рекурсивно находим медиану <tex>m</tex> в <tex>S</tex>. Используя <tex>m</tex>, уберем, хотя бы, <tex>n/4</tex> чисел среди <tex>n</tex>. Затем упакуем оставшиеся из <tex>n/g</tex> контейнеров в <tex>3n/4g</tex> контейнеров и затем продолжим рекурсию.