C>>Я пока не представляю себе, как это сделать без сортировки.
C>>Мне тутт по аське товарищ подсказал, что можно использовать более быструю поразрядную сортировку, но я думаю (сижу и думаю), как получить более изящное решение.

_JK>если это иметь ввиду под медианой то не вопрос за O(n*log(n)) ищется по такому же алгоритму как быстрая сортировка только без перестановок.

а еще в догонку вспомнил есть алгоритм нахождения такой медианы за линейное время это там где делится на части по 5 элементов ищется в них медиана потом они опять объединяются по 5 и т.д.