походу все-таки можно
я сам в шоке
нужен алгоритм BFPRT
алгоритм дает верхнуюю границу сложности поиска i-го порядкового элемента в массиве из n элементов следующего вида -- 103*n/18
в случае вашей задачи
- находим за линейное время элемент n/2
- находим за линейное время элемент n/2+1
- берем среднее арифметическое этих двух элементов
people.csail.mit.edu/rivest/pubs/BFPRT72.pdf -- вроде бы оригинал статьи об алгоритме
ru.wikipedia.org/wiki/BFPRT-Алгоритм -- версия в википедии
-----------------------------------------------------------------
P.S.
я протупил
описал как найти медиану
надо найти только элемент n/2 или n/2+1 в зависимости от направления сортировки