Cold & Serega
Serega
Я тут сравнивал сортировку слиянием и быструю сортировку, и застрял на том, как гарантировать O(n log n) в худшем случае, не жертвуя понятностью.
Cold
Используй стратегию выбора опорного элемента, чтобы избежать худшего расклада – бери медиану из трёх или случайный элемент, и добавь ограничение по глубине рекурсии, чтобы переключаться на пирамидальную сортировку, когда глубина превышает примерно 2 * log₂n. Код останется компактным, будет читаться как быстрая сортировка, и гарантирует O(n log n) в худшем случае.
Serega
Звучит неплохо, только помни про медиану из трёх – может подпортить, если данные уже частично отсортированы. Может, лучше сначала перемешай массив, потом выбирай середину, а сортировка кучей пусть будет подстраховкой. И, кстати, представь глубину рекурсии как барабанную дробь, не хочется, чтобы она превратилась в какофонию.
Cold
Ты прав, перестановка снижает этот риск, но добавляет O(n) накладных расходов. Защита по глубине – дешевка, но нужно подобрать плотный порог; 2·log₂n – неплохая отправная точка. Какие еще меры предосторожности рассматриваешь?
Serega
Да, добавь быструю проверку на уже отсортированные последовательности. Если массив почти отсортирован, просто переходи к сортировке вставками на небольших участках – так код останется чистым. И установи небольшой порог для перехода к сортировке вставками, когда подмассивы уменьшаются до, скажем, двадцати элементов; это не позволит рекурсии уйти вглубь и сохранит постоянные затраты на уровне. Сделай это модульным, чтобы каждый блок проверки ощущался как самостоятельное маленькое произведение, а не как запутанный хаос.
Cold
Отличная идея. Проверь, чтобы эта проверка не стоила дороже, чем польза. Держи пороги на уровне, и убедись, что переключатель вставки срабатывает только когда остаточный подмассив действительно незначителен. Так наши защиты останутся эффективными, а код – понятным.