Здравствуйте, _JoKe_, Вы писали:

_JK>Здравствуйте, Кодт, Вы писали:

_JK>а зачем тут что то сортировать?
_JK>за один проход ищем максимум и минимум используя две дополнительные переменные
_JK>делим сумму на два
_JK>за второй проход ищем наиболее приближенный к середине элемент.

_JK>итого 2N сравнений

_JK>зы: если за медиану считать среднеарифметическое значение от всего массива то в процессе поиска минимума и максимума заодно посчитать сумму.

_JK>возможно можно и быстрей надо подумать

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

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

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