длины N достаточно C * N * Log(N) операций. Для нахождения медианы — K * N. Я не помню всех алгоритмов, можно в Кнуте посмотреть, если интересно. Вообще, задача оценки сложности алгоритмов была подвергнута прямо-таки штурму в послевоенное время в США и у нас и в Европе.
Наводка. Если два массива длиной по N/2 уже упорядочены, то сколько нужно операций, чтобы упорядочить составной массив?
