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

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

Могу предположить, что это неправильный алгоритм: если на первом этапе мы отбрасываем хоть один элемент из любого подмассива, то можно принять меры, чтобы была отброшена именно медиана массива.