Смешанная производительность быстрой сортировки / слияния на случайных данных

Question

Тест попросил меня реализовать алгоритм сортировки, который сортирует массив, который, когда размер N> 1000 по сортировке слиянием, в противном случае по быстрой сортировке с осью выбирается случайным образом. Затем предположим, что сравниваемые ключи состоят из случайно распределенных целых чисел в [1, M]. Каким должен быть M для того, чтобы вышеприведенный алгоритм работал лучше всего?

Я позволил быстрой сортировке обрабатывать рекурсивный вызов сортировки слиянием, если размер <= 1000. На мой взгляд, из-за случайных ключей, случайных опорных точек и схемы разбиения Хоара повторяющиеся элементы не замедляются, если M намного меньше N, быстрая сортировка будет работать в лучшем виде, а сортировка слиянием выполняется одинаково для заданного значения * 1004. * размер массива независимо от распределения ключей, так для чего здесь используется M? </p>

Answer 1

Быстрая сортировка должна осуществляться осторожно, чтобы избежать патологических случаев. Выбор произвольной сводной точки - это хороший способ избежать квадратичной c сложности времени для отсортированных массивов, но этого недостаточно для массивов со многими дублирующимися элементами.

Если M намного меньше, чем N , у вас будет много дубликатов. Исходный алгоритм не обрабатывает дубликаты эффективно, и это приведет к значительному снижению производительности быстрой сортировки, поскольку оригинальный алгоритм Хоара удаляет только один элемент на уровень рекурсии для массивов со всеми идентичными элементами.

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