Выбор медианы
Я понимаю, что этот вопрос задавался миллион раз прежде, но я надеюсь, что это немного по-другому и немного более интересно. Я наткнулся на статью Дор и Цвик, в которой говорится, что можно найти медиану в массиве из n целых чисел в сравнениях <= 3n. Документ находится здесь: http://eccc.hpi-web.de/report/1995/031/download
Кто-нибудь когда-либо на самом деле реализовал это? Это кажется очень сложным, и я хотел бы увидеть его запуск, чтобы сравнить его с более стандартными версиями алгоритма.