C>А если массив будет, скажем, такой:
C>-3
C>1000000
C>-1
C>9
C>4

C>Медиана тут, очевидно, 4.

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

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