Из двух, используйте сортировку слиянием, когда вам нужна стабильная сортировка.Вы можете использовать измененную быструю сортировку (например, интросорт), когда вы этого не сделаете, поскольку она имеет тенденцию быть быстрее и использует меньше памяти.
Обычная старая быстрая сортировка, описанная Хоаром, довольно чувствительна к специальным убийствам производительности.случаи, которые делают его Theta(n^2), поэтому вам обычно требуется измененная версия.Вот где начинается распределение данных, так как сортировка слиянием не имеет плохих случаев.После того, как вы начнете модифицировать быструю сортировку, вы можете приступать ко всем видам различных настроек, и интросорт является одним из наиболее эффективных.Он на лету обнаруживает, является ли это убийственным случаем, и, если это так, переключается на heapsort.
На самом деле, базовая быстрая сортировка Hoare дает сбой в худшем случае для уже отсортированных данных, и поэтому ваши "хорошие тестовые случаи" с некоторымиуровень сортировки убьет его до некоторого уровня.Этот факт только для любопытства, поскольку для того, чтобы этого избежать, требуется всего лишь небольшая подстройка, ничего более сложного, чем весь процесс интросортировки.Поэтому даже проще анализировать версию, убитую отсортированными данными.
На практике в C ++ вы обычно используете std::stable_sort и std::sort, а не слишком беспокоитесь о точном алгоритме.