Когда сортировка слияния предпочтительнее, чем Quick sort?

Question

Быстрая сортировка намного лучше, чем сортировка слияния во многих случаях. Хотя, когда случаются случаи, когда сортировка слияния может быть лучшим решением, чем быстрое сортирование?

Например, сортировка слияний работает лучше, чем быстрая сортировка, когда данные не могут быть загружены в память сразу. Есть ли другие случаи?

РЕДАКТИРОВАТЬ: Ответы на предлагаемый дублированный вопрос список всех преимуществ быстрого сортировки по объему сортировки. Я спрашиваю здесь о возможных случаях, и приложения, использующие сортировку слияния, были бы полезны, чем использование быстрой сортировки.

Answer 1

Я, вероятно, должен начать с упоминания о том, что и quicksort, и mergesort могут работать нормально, если вы не можете сразу вместить все в память. Вы можете реализовать quicksort, выбирая точку поворота, затем перемещая элементы с диска в память и записывая элементы в один из двух разных файлов, основываясь на том, как этот элемент сравнивается с точкой опоры. Если вы используете двунаправленную очередь приоритетов, вы можете сделать это еще эффективнее, установив максимальное количество возможных элементов в память сразу.

Другие упоминали о том, что mergesort является наихудшим O (n log n), что определенно верно. Тем не менее, вы можете легко модифицировать quicksort, чтобы создать алгоритм introsort, гибрид между quicksort, insertion sort и heapsort, что в худшем случае O (n log n), но в большинстве случаев сохраняет скорость quicksort.

Возможно, было бы полезно узнать, почему quicksort обычно быстрее, чем mergesort, поскольку, если вы понимаете причины, вы можете довольно быстро найти некоторые случаи, когда mergesort является явным победителем. Quicksort, как правило, лучше, чем сортировка слияния по двум причинам:

1. Quicksort имеет лучшую локальность ссылок, чем слияние, что означает, что доступы, выполненные в быстрой сортировке, как правило, быстрее, чем соответствующие доступы в слиянии.

2. Quicksort использует наихудшую память O (log n) (если она выполнена правильно), в то время как mergesort требует O (n) памяти из-за накладных расходов на слияние.

Существует один сценарий, хотя эти преимущества исчезают. Предположим, вы хотите отсортировать связанный список элементов. Элементы связанного списка разбросаны по всей памяти, поэтому преимущество (1) исчезает (нет места ссылки). Во-вторых, связанные списки могут быть объединены только с служебными данными O (1) вместо O (n), поэтому преимущество (2) исчезает. Следовательно, вы обычно обнаружите, что mergesort является превосходным алгоритмом сортировки связанных списков, поскольку он делает меньше общих сравнений и не подвержен плохому выбору.

Надеюсь, это поможет!

Answer 2

Quicksort - средний случай O (n log n), но имеет наихудший случай O (n^2). Mergesort - всегда O (n log n). Помимо асимптотического наихудшего случая и загрузки памяти слияния, я не могу думать о другой причине.

Сценарии когда быстрая сортировка хуже, чем: слиянием

1. массив уже отсортирован.
2. Все элементы в массиве одинаковы.
3. Array сортирован в обратном порядке.

Возьмите слияние в quicksort, если вы ничего не знаете о данных.

Answer 3

Сорт слияния имеет гарантированный верхний предел O (N log N). Быстрая сортировка также имеет такой предел, но она намного выше - это O (N). Когда вам нужна гарантированная верхняя граница времени вашего кода, используйте сортировку слияния по быстрой сортировке.

Например, если вы пишете код для системы реального времени, который использует сортировку, выбор слияния будет лучшим выбором.

Answer 4

Одним из наиболее важных преимуществ сортировки слияний по быстрому сортированию является его стабильность: элементы по сравнению с ними сохраняют свой первоначальный порядок.

Answer 5

1. MergeSort стабильный по дизайну, равные элементы сохраняют свой первоначальный порядок.
2. MergeSort хорошо подходит для параллельной реализации (многопоточность).
3. MergeSort использует (около 30%) меньше сравнений, чем QuickSort. Это часто упускается из виду, потому что сравнение может быть довольно дорогостоящим (например, при сравнении нескольких полей строк базы данных).

Answer 6

1. Объединить Сортировку худшего случая сложность O (NlogN), тогда как Быстрая сортировку худшего случай O (N^2).
2. Merge Sort - стабильный вид, который означает, что один и тот же элемент в массиве сохраняет свои исходные позиции относительно друг друга.