Я нашел так много статей о медиане медианы, но нигде не нашел удовлетворительного ответа. Мой профессор научил меня топикам c, в которых он упомянул, что мы группируем данный массив размером 5 и находим медианы этих групп. сохраните их в другом массиве и рекурсивно выполняйте предыдущий шаг, пока мы не получим одну группу. Медиана этой группы будет медианой массива, и это может быть сделано в порядке n времени.
Но я не нашел того же в других учебниках и лекциях. Что упоминается, так это то, что результат делит массив на соотношение 30:70 в худшем случае.