статья wikipedia для сортировки слияния.
статья в википедии для быстрой сортировки.
Обе статьи имеют отличную визуализацию.
Оба имеют сложность n * log (n).
Таким образом, очевидно, что распределение данных будет влиять на скорость сортировки. Я предполагаю, что, поскольку сравнение может так же быстро сравнивать любые два значения, независимо от их распространения, диапазон значений данных не имеет значения.
Более важно учитывать боковое распределение (направление х) относительно упорядочения (снятая величина).
Хорошим тестовым примером для рассмотрения было бы, если бы тестовые данные имели некоторый уровень сортировки...
В то время как Java 6 и более ранние версии используют сортировку слияния как алгоритмы сортировки, С# использует QuickSort в качестве алгоритма сортировки.
QuickSort работает лучше, чем слияние, даже если они оба O (nlogn). QuickSort имеет меньшую константу, чем сортировка слияния.
Обычно это зависит от используемых структур данных. Быстрая сортировка
как правило, самый быстрый, но он не гарантирует O (n * log (n)); есть
когда он становится O (n ^ 2). Сорт кучи - обычный
альтернатива; он гарантирует O (n * log (n)), независимо от начального порядка,
но он имеет гораздо более высокий постоянный коэффициент. Он обычно используется, когда вы
требуется жесткий верхний предел времени. Некоторые более свежие алгоритмы
используйте быструю сортировку, но попытайтесь распознать, когда она начнет дегенерировать,
и затем переключитесь на кучу. Сортировка слияния используется, когда данные
структура не поддерживает произвольный доступ, поскольку она работает с чистым
последовательный доступ (форвардные итераторы, а не произвольный доступ
итераторы). Например, он используется в std::list<>::sort. Это также
широко используется для внешней сортировки, где произвольный доступ может быть очень, очень
дорогой по сравнению с последовательным доступом. (При сортировке файла, который
не вписывается в память, вы можете разбить его на куски, которые вписываются в
память, сортируйте их с помощью quicksort, записывая каждый файл в файл, затем
merge сортировать созданные файлы.)
Mergesort быстрее работает со связанными списками. Это связано с тем, что указатели могут быть легко изменены при слиянии списков. Для этого требуется только один проход (O (n)) через список.
Быстрое сокращение алгоритма на месте требует перемещения (свопинга) данных. Хотя это может быть очень эффективным для набора данных в памяти, это может быть намного дороже, если ваш набор данных не подходит в памяти. Результатом будет много ввода-вывода.
В наши дни происходит много распараллеливаний. Параллелизация Mergesort проще, чем Quicksort (на месте). Если не использовать алгоритм на месте, то сложность пространства для quicksort равна O (n), которая является той же самой, что и mergesort.
Итак, чтобы обобщить, quicksort, вероятно, более эффективна для наборов данных, которые вписываются в память. Для вещей, которые больше, лучше использовать mergesort.
Другим общим временем использования mergesort по quicksort является то, что данные очень похожи (то есть не близки к равномерным). Quicksort опирается на использование стержня. В случае, когда все значения совпадают, quicksort попадает в худший случай O (n ^ 2). Если значения данных очень схожи, то более вероятно, что будет выбран слабый стержень, ведущий к очень неуравновешенным разделам, ведущим к O (n ^ 2) времени исполнения. Самый простой пример: если все значения в списке совпадают.
Существует реальный алгоритм сортировки - Timsort - он использует идею о том, что данные, встречающиеся в дикой природе, часто частично сортируются.
Алгоритм основан на сортировке и сортировке слияния и используется в CPython, Java 7 и Android.
Подробнее см. статью Википедии.
Из двух используйте сортировку слияния, когда вам нужен стабильный вид. Вы можете использовать модифицированную quicksort (например, introsort), когда вы этого не сделаете, поскольку она имеет тенденцию быть быстрее и использует меньше памяти.
Обычный старый Quicksort, как описано Hoare, довольно чувствителен к специальным случаям, убивающим большие числа, которые делают его Theta(n^2), поэтому вам обычно нужна модифицированная версия. То, где происходит распространение данных, поскольку сортировка слияния не имеет плохих случаев. После того, как вы начнете изменять quicksort, вы можете продолжать всевозможные твики, а интросорт - один из наиболее эффективных. Он обнаруживает на лету ли это в случае с убийцей, и если это так переключается на heapsort.
Фактически, самый простой Quicksort от Hoare не подходит для уже отсортированных данных, поэтому ваши "хорошие тестовые примеры" с некоторым уровнем сортировки убьют его до некоторого уровня. Однако этот факт относится только к любопытству, поскольку для его устранения требуется лишь небольшая настройка, не такая сложная, как переход к интросортированию. Поэтому упростить даже анализировать версию, убитую отсортированными данными.
На практике в С++ вы обычно использовали std::stable_sort и std::sort, а не слишком беспокоились о точном алгоритме.
Помните на практике, если у вас нет очень большого набора данных и/или выполняете сортировку много раз, это, вероятно, вообще не имеет значения. При этом quicksort обычно считается "самым быстрым" n * log (n) сортировщиком. См. Заданный вопрос: Быстрая сортировка и сортировка сортировки