алгоритмы - Как использовать алгоритм, чтобы за линейное время найти любую порядковую статистику массива?

Ищем медиану и создаем новый массив, ставим ее посередине. Слева от нее поставим все элементы, которые меньше медианы, справа - те, которые больше. Всего мы выполнили $%Cn$% действий (C-какая-то константа). Теперь если запрошенная порядковая статистика $%k<\frac{n}{2}$%, делаем тоже самое с левой частью массива. Если больше, то с правой, пересчитав $%k=k-\frac{n}{2}$%. Если $%k=\frac{n}{2}$%, то найденная медиана и есть запрошенная порядковая статистика. Каждый раз мы ищем статистику в массива, который в два раза меньше предыдущего. Итого $%C(n+\frac{n}{2}+\frac{n}{4}+\cdots)< C2n$% действий, 2 - константа, которую можно убрать в $%C$% $%\Rightarrow $% асимптотика $%O(n)$%. Нужно только обратить внимание на случай, когда $%n$% - четное, но это детали реализации.