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

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

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

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

Ответы

Ответ 1

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

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

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

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

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

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

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

Сценарии, когда quicksort хуже, чем mergesort:

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

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

Ответ 6

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