Ответ 1
Основное отличие состоит в том, что сортировка слияния делает больше ходов, но меньше сравнений, чем быстрый сортировка. Даже в случае сортировки массива родных типов быстрая сортировка только на 15% быстрее, по крайней мере, когда я протестировал ее на больших массивах псевдослучайных 64-битных целых без знака, которые должны быть быстрыми, лучше всего, на моем (Intel 3770K 3.5ghz, Windows 7 Pro 64 бит, Visual Studio 2015, сортировка 16 миллионов псевдослучайных 64-битных целых без знака, 1,32 секунды для быстрой сортировки, 1,55 секунды для сортировки слияния, 1,32/1,55 ~ = 0,85, поэтому быстрая сортировка была примерно на 15% быстрее, чем сортировка слияния). Мой тест был с быстрой сортировкой, у которой не было проверок, чтобы избежать наихудшего случая O (n ^ 2) или O (n). Поскольку проверки добавляются к быстрому сортировке, чтобы уменьшить или предотвратить поведение в худшем случае (например, вернуться к сортировке кучи, если рекурсия становится слишком глубокой), преимущество скорости уменьшается до менее 10% (что является разницей между реализацией VS2015 std:: sort (изменение быстрого сортировки) по сравнению с std:: stable_sort (измененная сортировка слияния).
Если сортировка "строк", более вероятно, что то, что сортируется, представляет собой массив указателей (или ссылок) на эти строки. В этом случае сортировка слияния выполняется быстрее, потому что ходы включают указатели, тогда как сравнения включают уровень косвенности и сравнение строк.
Основная причина выбора быстрой сортировки по сортировке слияния - это не скорость, а потребность в пространстве. Сортировка слияния обычно использует второй массив того же размера, что и оригинал. Быстрая сортировка и сортировка слияния сверху вниз также требуют логарифмических (n) стековых фреймов для рекурсии и для быстрого стека стека для сортировки для лог-кадров (n) стека выполняется только путем рекурсии на меньшем разделе и циклического возврата для обработки большего раздела.
В терминах проблем с кешем большинство современных процессоров имеют 4 или 8 ассоциативных кэши. Для сортировки слияния во время слияния два входа запускаются в 2 строки кэша, а один вывод выполняется в третьей строке кэша. Быстрый поиск сканирует данные перед выполнением свопов, поэтому отсканированные данные будут находиться в кеше, хотя в отдельных строках, если два элемента, которые сравниваются/заменены, расположены достаточно далеко друг от друга.
Для внешнего сортировки используется некоторая вариация сортировки слияния снизу вверх. Это связано с тем, что операции слияния сортировки слияния являются последовательными (возможен единственный случайный доступ при запуске новой пары прогонов), которая выполняется быстро в случае жестких дисков или в устаревшем режиме, ленточные накопители (требуется не менее 3 ленточных накопителей). Каждое чтение или запись может быть для очень больших блоков данных, что сокращает среднее время доступа к каждому элементу в случае жесткого диска, поскольку большое количество элементов считывается или записывается одновременно с каждым вводом/выводом.
Следует также отметить, что большинство сортировок слияний в библиотеках также являются некоторыми вариантами сортировки слияния снизу вверх. Сверху сортировка слияния - это в основном реализация учебной среды.
При сортировке массива собственных типов на процессоре с 16 регистрами, таких как X86 в режиме 64 бит, 8 регистров, используемых в качестве начальных + конечных указателей (или ссылок) для 4 сеансов, затем с 4-сторонним слиянием сортировка часто примерно такая же или немного быстрее, чем быстрая сортировка, предполагая, что компилятор оптимизирует указатели или ссылки для регистрации. Это аналогичный компромисс, как и быстрая сортировка, сортировка с 4-сторонним слиянием больше сравнивает (1,5 x сравнивает), но меньше ходов (0.5 x перемещается), чем традиционная сортировка с двумя способами.
Следует отметить, что эти сорта связаны cpu, а не связаны с памятью. Я сделал многопоточную версию сортировки слияния снизу вверх, а в случае использования 4 потоков сортировка была в 3 раза быстрее. Ссылка на пример кода Windows с использованием 4 потоков:
https://codereview.stackexchange.com/info/148025/multithreaded-bottom-up-merge-sort