Изменения

Разбиваем наш массив на группы по 5 элементов(на самом деле можно разбивать и на другое нечетное количество элементов больших 5). Затем в каждой группе находим средний элемент(медиану), это можно сделать любой сортировкой. И запускаем рекурсивно этот алгоритм от медиан. Тем самым мы найдем средний элемент среди медиан, то есть медиану медиан. Эту медиану медиан выберем рассекающим элементом для поиска <tex>k</tex>-го элемента. Далее разбиваем массив на две части : слева от рассекающего элемента числа меньшие него, а справа - числа больше рассекающего элемента или равные ему. И рекурсивно запускаем наш алгоритм от той части массива, в котором будет лежать <tex>k</tex>-й элемент.