почему быстрая сортировка лучше, чем слияние?

<p>мне задавали этот вопрос во время интервью. они оба o(nlogn), и все же большинство людей используют quicksort вместо mergesort. это почему?</p>

<p>быстрая сортировка имеет o (<i>n</i><sup>2</sup>) время выполнения в худшем случае и o (<i>n</i>журнал<i>n</i>среднее время выполнения. однако во многих сценариях предпочтительнее сортировка слиянием, поскольку многие факторы влияют на время выполнения алгоритма, и, собрав их все вместе, выигрывает быстрая сортировка.</p><p>в частности, часто цитируемое время выполнения алгоритмов сортировки относится к числу сравнений или количеству перестановок, необходимых для сортировки данных. это действительно хороший показатель производительности, особенно потому, что он не зависит от базовой конструкции оборудования. однако другие вещи, такие как локальность ссылок (т. е. читаем ли мы много элементов, которые, вероятно, находятся в кеше?), также играют важную роль на современном оборудовании. в частности, для быстрой сортировки требуется мало дополнительного пространства, и она обладает хорошей локальностью кэша, что во многих случаях делает это быстрее, чем сортировка слиянием.</p><p>кроме того, очень легко избежать наихудшего времени выполнения быстрой сортировки o (<i>n</i><sup>2</sup>) почти полностью, используя соответствующий выбор центра, например, выбирая его случайным образом (это отличная стратегия).</p><p>на практике многие современные реализации быстрой сортировки (в частности, <code>std::sort</code> в libstdc ++) на самом деле <a href="http://en.wikipedia.org/wiki/introsort">introsort</a> , теоретический наихудший случай которого равен o (<i>n</i>журнал<i>n</i>), так же, как сортировка слиянием. это достигается путем ограничения глубины рекурсии и переключения на другой алгоритм ( <a href="http://en.wikipedia.org/wiki/heapsort">heapsort</a> ), когда он превышает log<i>n</i>,.</p>

<p>как отмечают многие, средняя производительность по случаям быстрой сортировки быстрее, чем сортировка слиянием. <strong>но</strong> это верно только в том случае, если вы предполагаете постоянное время для доступа к любому фрагменту памяти по требованию.</p><p>в ram это предположение обычно не так уж плохо (оно не всегда верно из-за кешей, но не так уж плохо). однако, если ваша структура данных достаточно велика, чтобы жить на диске, то быстрая сортировка <em> уничтожается </em> из-за того, что ваш средний диск выполняет примерно 200 случайных операций поиска в секунду. , но этот же диск не имеет проблем при последовательном чтении или записи мегабайт в секунду данных. именно это и делает mergesort.</p><p>поэтому, если данные должны быть отсортированы на диске, вам действительно нужно использовать некоторые варианты сортировки слиянием. (обычно вы быстро сортируете подсписки, а затем начинаете объединять их вместе, превышая некоторый порог размера.)</p><p>более того, если вам нужно <em> сделать что-нибудь </em> с наборами данных такого размера, подумайте о том, как избежать поиска на диске. например, именно поэтому это стандартный совет: перед выполнением больших загрузок данных в базы данных отбрасывать индексы, а затем перестраивать индекс позже. поддержание индекса во время загрузки означает постоянный поиск на диске. напротив, если вы отбрасываете индексы, то база данных может перестроить индекс, сначала отсортировав информацию, с которой нужно иметь дело (конечно, используя сортировку слиянием!), а затем загрузив ее в структуру данных btree для индекса. (btrees естественно поддерживаются в порядке, поэтому вы можете загрузить один из отсортированного набора данных с несколькими поисками на диск.)</p><p>был ряд случаев, когда понимание того, как избежать поиска диска, позволило мне сделать работу по обработке данных часами, а не днями или неделями.</p>

<p>на самом деле quicksort - это o (n<sup>2</sup>). его <em>в среднем случае</em> время выполнения равно o (nlog (n)), но его <em>в худшем случае</em> равно o (n<sup>2</sup>), который происходит, когда вы запускаете его в списке, который содержит несколько уникальных элементов. рандомизация занимает o (n). конечно, это не меняет наихудшего случая, оно просто предотвращает длительную работу злоумышленника.</p><p>quicksort более популярен, потому что:</p><ol> <li>на месте (mergesort требует дополнительной памяти, линейной по количеству сортируемых элементов).</li> <li>имеет небольшую скрытую константу.</li> </ol>

<p>"и все же большинство людей используют quicksort вместо mergesort. почему?"</p><p>одна психологическая причина, которая не была дана, состоит в том, что quicksort назван более умно. т.е. хороший маркетинг.</p><p>да, быстрая сортировка с тройным разделением, вероятно, является одним из лучших алгоритмов сортировки общего назначения, но при этом не следует забывать о том, что "быстрая" сортировка звучит гораздо более мощно, чем сортировка "слияние".</p>

<p>как уже отмечалось, наихудшим случаем быстрой сортировки является o (n ^ 2), тогда как сортировка слиянием и heapsort остаются на уровне o (nlogn). в среднем, однако, все три являются o (nlogn); поэтому они в подавляющем большинстве случаев сопоставимы.</p><p>что делает quicksort лучше в среднем, так это то, что внутренний цикл подразумевает сравнение нескольких значений с одним, тогда как в двух других оба термина различны для каждого сравнения. другими словами, quicksort выполняет вдвое меньше операций чтения, чем два других алгоритма. на современных процессорах производительность сильно зависит от времени доступа, поэтому в итоге quicksort станет отличным выбором.</p>

<p>я хотел бы добавить, что из трех упомянутых выше алгоритмов (mergesort, quicksort и heap sort) только mergesort является стабильным. то есть порядок не изменяется для тех значений, которые имеют одинаковый ключ. в некоторых случаях это желательно.</p><p>но, по правде говоря, большинству людей нужна только хорошая средняя производительность, а быстрая сортировка ... быстрая =)</p><p>все алгоритмы сортировки имеют свои взлеты и падения. смотрите <a href="http://en.wikipedia.org/wiki/sorting\_algorithm#classification">статья в википедии об алгоритмах сортировки</a> для хорошего обзора.</p>

<p>от <a href="http://en.wikipedia.org/wiki/quicksort">запись в википедии о быстрой сортировке</a> :</p><blockquote> <p>quicksort также конкурирует с mergesort, другим алгоритмом рекурсивной сортировки, но с преимуществом времени выполнения running (nlogn) в худшем случае. mergesort является стабильной сортировкой, в отличие от быстрой сортировки и heapsort, и может быть легко адаптирован для работы со связанными списками и очень большими списками, хранящимися на медленных носителях доступа, таких как дисковое хранилище или сетевое хранилище. хотя быстрая сортировка может быть написана для работы со связанными списками, она часто страдает от неудачного выбора сводных данных без произвольного доступа. основным недостатком сортировки слиянием является то, что при работе с массивами в лучшем случае требуется θ (n) вспомогательного пространства, тогда как вариант быстрой сортировки с разделением на месте и хвостовой рекурсией использует только пространство log (logn). (обратите внимание, что при работе со связанными списками для сортировки слиянием требуется только небольшой постоянный объем вспомогательного хранилища.)</p> </blockquote>

<p> <a href="http://en.wikipedia.org/wiki/mu\_(negative)">mu!</a> быстрая сортировка не лучше, она хорошо подходит для другого типа приложений, чем слияние.</p><blockquote> <p>mergesort стоит учитывать, если скорость важна, плохая производительность в худшем случае недопустима и доступно дополнительное пространство . <a href="http://en.wikipedia.org/wiki/mu\_(negative)">1</a> </p> </blockquote><p>вы заявили, что они "они оба o(nlogn) […]". это не верно. "quicksort использует около n ^ 2/2 сравнений в худшем случае." <a href="http://en.wikipedia.org/wiki/mu\_(negative)">1</a> .</p><p>однако, по моему опыту, наиболее важным свойством является простота реализации последовательного доступа, который вы можете использовать при сортировке при использовании языков программирования с императивной парадигмой.</p><p> <a href="http://en.wikipedia.org/wiki/mu\_(negative)">1</a> седжвик, алгоритмы</p>

<p>быстрая сортировка является самым быстрым алгоритмом сортировки на практике, но имеет ряд патологических случаев, которые могут заставить его работать так же плохо, как o (n2).</p><p>heapsort гарантированно работает в o (n * ln (n)) и требует только конечного дополнительного хранилища. но есть много цитат из реальных тестов, которые показывают, что heapsort значительно медленнее, чем quicksort в среднем.</p>

<p>объяснение википедии:</p><blockquote> <p>как правило, быстрая сортировка на практике значительно быстрее, чем другие алгоритмы θ (nlogn), потому что ее внутренний цикл может быть эффективно реализован на большинстве архитектур, а в большинстве реальных данных можно сделать выбор проекта, который сводит к минимуму вероятность необходимости квадратичного времени ,.</p> </blockquote><p> <a href="http://en.wikipedia.org/wiki/quicksort">quicksort</a> </p><p> <a href="http://en.wikipedia.org/wiki/mergesort">слияние</a> </p><p>я думаю, что есть также проблемы с объемом памяти, необходимым для mergesort (то есть ω (n)), которого нет в реализациях быстрой сортировки. в худшем случае это одинаковое количество алгоритмического времени, но сортировка слиянием требует больше памяти.</p>

<p>я хотел бы добавить к существующим отличным ответам некоторую математику о том, как quicksort работает при отклонении от лучшего случая и насколько это вероятно, что, я надеюсь, поможет людям немного лучше понять, почему случай с o (n ^ 2) не является реальным озабоченность в отношении более сложных реализаций quicksort.</p><p>помимо проблем произвольного доступа, есть два основных фактора, которые могут повлиять на производительность быстрой сортировки, и оба они связаны с тем, как сводка сравнивается с сортируемыми данными.</p><p>1) небольшое количество ключей в данных. набор данных с одним и тем же значением будет отсортирован за n ^ 2 раз на быстрой сортировке с двумя разделами vanilla, потому что все значения, кроме местоположения центра, каждый раз располагаются на одной стороне. современные реализации решают эту проблему такими методами, как использование 3-секционной сортировки. эти методы выполняются для набора данных с одинаковым значением во время o(n). таким образом, использование такой реализации означает, что ввод с небольшим количеством клавиш фактически увеличивает время выполнения и больше не является проблемой.</p><p>2) чрезвычайно неудачный выбор точки поворота может привести к ухудшению производительности. в идеальном случае опорная точка всегда будет такой, что 50% данных будут меньше, а 50% - больше, так что вход будет разбит пополам во время каждой итерации. это дает нам n сравнений и меняет время log-2 (n) рекурсий на o (n * logn).</p><p><strong> насколько неидеальный выбор сводки влияет на время выполнения? </strong></p><p>давайте рассмотрим случай, когда стержень последовательно выбирается таким образом, что 75% данных находятся на одной стороне стержня. это все еще o (n * logn), но теперь база журнала изменилась на 1/0,75 или 1,33. отношение в производительности при изменении базы всегда является константой, представленной log (2)/log (newbase). в этом случае эта константа равна 2,4. так что это качество выбора разворота занимает в 2,4 раза больше времени, чем идеальное.</p><p><strong> как быстро это ухудшается? </strong></p><p>не очень быстро, пока выбор центра не станет (последовательно) очень плохим:</p><ul> <li>50% с одной стороны: (идеальный случай)</li> <li>75% с одной стороны: в 2,4 раза больше</li> <li>90% с одной стороны: в 6,6 раза больше</li> <li>95% с одной стороны: в 13,5 раза больше</li> <li>99% с одной стороны: в 69 раз больше</li> </ul><p>когда мы приближаемся к 100% с одной стороны, логическая часть выполнения приближается к n, и все выполнение асимптотически приближается к o (n ^ 2).</p><p>в простой реализации quicksort такие случаи, как отсортированный массив (для сводки 1-го элемента) или массив с обратной сортировкой (для сводки последнего элемента), будут надежно создавать время выполнения o (n ^ 2) в худшем случае. кроме того, реализации с предсказуемым выбором поворота могут подвергаться dos-атаке с помощью данных, предназначенных для выполнения в худшем случае. современные реализации избегают этого с помощью различных методов, таких как рандомизация данных перед сортировкой, выбор медианы из 3 случайно выбранных индексов и т.д. с этой рандомизацией в миксе мы имеем 2 случая:</p><ul> <li>небольшой набор данных. наихудший случай вполне возможен, но o (n ^ 2) не является катастрофическим, потому что n достаточно мало, поэтому n ^ 2 также мало.</li> <li>большой набор данных. худший случай возможен в теории, но не на практике.</li> </ul><p><strong> насколько вероятно, что мы увидим ужасную производительность? </strong></p><p>шансы <em> исчезающе малы </em>. давайте рассмотрим своего рода 5000 значений:</p><p>наша гипотетическая реализация выберет опорную точку, используя медиану из 3 случайно выбранных индексов. мы будем рассматривать "точки", которые находятся в диапазоне 25% -75%, как "хорошие", а точки, которые находятся в диапазоне 0% -25% или 75% -100%, являются "плохими". если вы посмотрите на распределение вероятностей, используя медиану из 3 случайных индексов, у каждой рекурсии есть шанс 11/16 закончиться хорошим разворотом. давайте сделаем 2 консервативных (и ложных) предположения для упрощения математики:</p><ol> <li> <p>хорошие точки разворота всегда точно на 25%/75% и работают в 2,4 * идеальном случае. мы никогда не получим идеальное разделение или любое разделение лучше, чем 25/75.</p> </li> <li> <p>плохие точки всегда являются наихудшим случаем и, по сути, не способствуют решению проблемы.</p> </li> </ol><p>наша реализация quicksort остановится на n = 10 и переключится на сортировку вставкой, поэтому нам потребуется 22 25%/75% pivot-разделов, чтобы разбить входное значение 5000 на такую глубину. (10 * 1.333333 ^ 22> 5000) или нам нужно 4990 наихудших опорных точек. имейте в виду, что если мы накопим 22 хороших пивота в <em> любой точке </em>, тогда сортировка будет завершена, поэтому наихудший случай или что-то рядом с ним требует <em> чрезвычайно </em> невезение. если бы нам потребовалось 88 рекурсий для фактического достижения 22 хороших опорных точек, необходимых для сортировки до n = 10, это было бы в 4 * 2,4 * идеальном случае или примерно в 10 раз больше времени выполнения идеального случая. насколько вероятно, что мы <em> не </em> достигнем требуемых 22 хороших точек после 88 рекурсий?</p><p> <a href="http://vassarstats.net/textbook/ch5apx.html">биномиальное распределение вероятностей</a> может ответить на этот вопрос, и ответ составляет около 10 ^ -18. (n равно 88, k равно 21, p равно 0,6875) вероятность удара молнии в течение 1 секунды, необходимого для нажатия кнопки [сортировка], у вашего пользователя примерно в тысячу раз выше, чем при выполнении 5000 операций сортировки элементов <em> чуть хуже </em>, чем в 10 * идеальном случае. этот шанс уменьшается по мере увеличения набора данных. вот некоторые размеры массивов и их соответствующие шансы работать дольше 10 * идеально:</p><ul> <li>массив из 640 предметов: 10 ^ -13 (требуется 15 хороших точек разворота из 60 попыток)</li> <li>массив из 5000 элементов: 10 ^ -18 (требуется 22 хороших пивота из 88 попыток)</li> <li>массив из 40000 элементов: 10 ^ -23 (требуется 29 хороших опорных точек из 116)</li> </ul><p>помните, что это с двумя консервативными предположениями, которые хуже, чем реальность. таким образом, фактическая производительность еще лучше, а баланс оставшейся вероятности ближе к идеалу, чем нет.</p><p>наконец, как уже упоминали другие, даже эти невероятно маловероятные случаи можно устранить, переключившись на сортировку кучи, если стек рекурсии заходит слишком глубоко. таким образом, tldr заключается в том, что для хороших реализаций quicksort наихудший случай <em> на самом деле не существует </em>, поскольку он был разработан и выполнение завершается за время o (n * logn).</p>

<p>быстрая сортировка не лучше, чем слияние. с o (n ^ 2) (наихудший случай, который редко случается), быстрая сортировка потенциально намного медленнее, чем o(nlogn) сортировки слиянием. quicksort имеет меньше накладных расходов, поэтому с маленькими и медленными компьютерами это лучше. но компьютеры сегодня настолько быстры, что дополнительные издержки сортировки слиянием незначительны, и риск очень медленной быстрой сортировки намного превышает незначительные издержки сортировки слиянием в большинстве случаев.</p><p>кроме того, сортировка слиянием оставляет элементы с одинаковыми ключами в их первоначальном порядке полезным атрибутом.</p>

<p>в отличие от сортировки слиянием, быстрая сортировка не использует вспомогательное пространство. в то время как сортировка слиянием использует вспомогательное пространство o (n). но сортировка слиянием имеет наихудшую временную сложность o(nlogn), тогда как быстрая сортировка наихудшего случая - это o (n ^ 2), которая происходит, когда массив уже отсортирован.</p>

<p>ответ будет слегка отклонен в сторону быстрой сортировки с изменениями, внесенными с помощью dualpivotquicksort для примитивных значений. он используется в <strong> java 7 </strong> для сортировки в <strong> java.util.arrays </strong></p><pre><code>it is proved that for the dual-pivot quicksort the average number of comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n), whereas classical quicksort algorithm has 2*n*ln(n) and 1*n*ln(n) respectively. full mathematical proof see in attached proof.txt and proof\_add.txt files. theoretical results are also confirmed by experimental counting of the operations. </code></pre><p>вы можете найти реализацию java7 здесь - <a href="http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/arrays.java">http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/arrays.java</a> </p><p>дальнейшее удивительное чтение на dualpivotquicksort - <a href="http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628">http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628</a> </p>

<p>в сортировке слиянием общий алгоритм:</p><ol> <li>сортировать левый под-массив</li> <li>сортировать правильный под-массив</li> <li>объединить 2 отсортированных подмассива</li> </ol><p>на верхнем уровне объединение 2 отсортированных подмассивов включает в себя работу с n элементами.</p><p>на один уровень ниже, каждая итерация шага 3 включает в себя работу с n/2 элементами, но вы должны повторить этот процесс дважды. таким образом, вы по-прежнему имеете дело с 2 * n/2 == n элементами.</p><p>на один уровень ниже, вы объединяете 4 * n/4 == n элементов и так далее. каждая глубина в рекурсивном стеке включает в себя объединение одинакового количества элементов во всех вызовах для этой глубины.</p><p>вместо этого рассмотрим алгоритм быстрой сортировки:</p><ol> <li>выберите опорную точку</li> <li>поместите опорную точку в правильном месте в массиве, со всеми меньшими элементами слева, и большими элементами справа</li> <li>сортировать левый подмассив</li> <li>сортировать правый подмассив</li> </ol><p>на верхнем уровне вы имеете дело с массивом размера n. затем вы выбираете одну точку разворота, устанавливаете ее в правильное положение, а затем можете полностью ее игнорировать для остальной части алгоритма.</p><p>на один уровень ниже, вы имеете дело с 2 подмассивами, которые имеют объединенный размер n-1 (т.е. вычитаете предыдущую точку разворота). вы выбираете опорную точку для каждого подмассива, что дает до 2 дополнительных опорных точек.</p><p>на один уровень ниже, вы имеете дело с 4 поднаборами объединенного размера n-3 по тем же причинам, что и выше.</p><p>затем n-7 ... затем n-15 ... затем n-32 ...</p><p>глубина вашего рекурсивного стека остается примерно одинаковой (logn). с сортировкой слиянием вы всегда имеете дело с n-элементным слиянием на каждом уровне рекурсивного стека. однако при быстрой сортировке количество элементов, с которыми вы имеете дело, уменьшается при переходе в стек. например, если вы посмотрите на глубину посередине рекурсивного стека, число элементов, с которыми вы имеете дело, равно n - 2 ^ ((logn)/2)) == n - sqrt (n).</p><p>отказ от ответственности: при сортировке слиянием, поскольку вы каждый раз делите массив на 2 абсолютно равных блока, рекурсивная глубина равна logn. при быстрой сортировке, поскольку ваша точка вращения вряд ли находится точно в середине массива, глубина вашего рекурсивного стека может быть немного больше, чем logn. я не делал математики, чтобы увидеть, насколько большую роль этот фактор и фактор, описанный выше, на самом деле играют в сложности алгоритма.</p>

<p>быстрая сортировка имеет среднюю сложность, но в некоторых приложениях это неправильный выбор. быстрая сортировка уязвима для атак отказа в обслуживании. если злоумышленник может выбрать входные данные для сортировки, он может легко создать набор, который требует наихудшего временного усложнения o (n ^ 2).</p><p>средняя сложность mergesort и сложность наихудшего случая одинаковы, и, как таковая, не сталкивается с одной и той же проблемой. это свойство сортировки слиянием также делает его лучшим выбором для систем реального времени - именно потому, что нет патологических случаев, которые заставляют его работать намного, намного медленнее.</p><p>по этим причинам я больше поклонник mergesort, чем quicksort.</p>

<p>хотя они оба находятся в одном классе сложности, это не значит, что они оба имеют одинаковое время выполнения. быстрая сортировка обычно быстрее, чем сортировка слиянием, просто потому, что проще кодировать жесткую реализацию, а выполняемые ею операции могут выполняться быстрее. это потому, что быстрая сортировка обычно быстрее, чем люди используют ее вместо сортировки слиянием.</p><p>тем не мение! я лично часто использую сортировку слиянием или вариант быстрой сортировки, которая ухудшается до сортировки слиянием, когда быстрая сортировка работает плохо. помните. быстрая сортировка только o (n log n) в среднем <em> </em>. это наихудший случай o (n ^ 2)! mergesort всегда o (n log n). в случаях, когда производительность или скорость реагирования в реальном времени являются обязательными, а ваши входные данные могут поступать из злонамеренного источника, <strong>вы не должны использовать простую быструю сортировку.</strong></p>

<p>быстрая сортировка - наихудший случай o (n ^ 2), однако в среднем случае последовательно выполняется сортировка слиянием каждый алгоритм - o (nlogn), но вы должны помнить, что, говоря о big o, мы не учитываем более низкие факторы сложности. быстрая сортировка значительно улучшена по сравнению с сортировкой слиянием, когда речь идет о постоянных факторах.</p><p>сортировка слиянием также требует o(2n) памяти, в то время как быстрая сортировка может быть выполнена на месте (требуя только o (n)). это еще одна причина, по которой быстрая сортировка обычно предпочтительнее сортировки слиянием.</p><p><strong>дополнительная информация:</strong></p><p>наихудший случай быстрой сортировки возникает, когда стержень плохо выбран. рассмотрим следующий пример:</p><p>[5, 4, 3, 2, 1]</p><p>если в качестве наименьшего или наибольшего числа в группе выбрано значение pivot, то быстрая сортировка будет выполняться за o (n ^ 2). вероятность выбора элемента, который находится в наибольшем или наименьшем 25% списка, составляет 0,5. это дает алгоритму шанс 0.5 быть хорошим стержнем. если мы используем типичный алгоритм поворота выбора (скажем, выбирая случайный элемент), мы имеем 0,5 шанса выбрать хороший стержень для каждого выбора оси. для коллекций большого размера вероятность всегда выбирать плохой шарнир составляет 0,5 * n. на основании этой вероятности быстрая сортировка эффективна для среднего (и типичного) случая.</p>

<p><strong> почему быстрая сортировка хороша? </strong></p><ul> <li>quicksort занимает n ^ 2 в худшем случае и nlogn в среднем. худший случай происходит, когда данные отсортированы. это может быть смягчено случайным перемешиванием перед началом сортировки.</li> <li>быстрая сортировка не требует дополнительной памяти, занимаемой сортировкой слиянием.</li> <li>если набор данных большой и в нем присутствуют идентичные элементы, сложность быстрой сортировки уменьшается с помощью трехстороннего разделения. больше нет идентичных предметов, лучше сортировка. если все элементы идентичны, они сортируются по линейному времени. [это реализация по умолчанию в большинстве библиотек]</li> </ul><p><strong> quicksort всегда лучше, чем mergesort? </strong></p><p><strong> не совсем. </strong></p><ul> <li>mergesort стабилен, а quicksort - нет. поэтому, если вам нужна стабильность в выводе, вы должны использовать mergesort. стабильность требуется во многих практических применениях.</li> <li>память дешевая в наше время. поэтому, если дополнительная память, используемая mergesort, не критична для вашего приложения, использование mergesort не повредит.</li> </ul><p><strong> примечание: </strong> в java функция arrays.sort () использует quicksort для примитивных типов данных и mergesort для типов данных объектов. поскольку объекты потребляют служебную память, поэтому добавленные небольшие накладные расходы для mergesort могут не представлять проблемы с точки зрения производительности.</p><p><strong> справка </strong>: посмотрите видеоролики quicksort о <a href="https://class.coursera.org/algs4parti-003/lecture/index">-я неделя, курс алгоритмов принстона на coursera</a> </p>

<p>это довольно старый вопрос, но так как я недавно имел дело с обоими, вот мой 2c:</p><p>сортировка слиянием требует в среднем ~ n log n сравнений. для уже (почти) отсортированных массивов это уменьшается до 1/2 n log n, поскольку при слиянии мы (почти) всегда выбираем "левую" часть 1/2 n раз, а затем просто копируем правые 1/2 n элементы. кроме того, я могу предположить, что уже отсортированный ввод заставляет предсказатель ветвления процессора сиять, но угадывает почти все ответвления правильно, предотвращая тем самым задержки конвейера.</p><p>быстрая сортировка в среднем требует ~ 1,38 n log n сравнений. он не очень выигрывает от уже отсортированного массива с точки зрения сравнений (однако он дает преимущества с точки зрения перестановок и, вероятно, с точки зрения предсказаний переходов внутри цп).</p><p>мои тесты на довольно современном процессоре показывают следующее:</p><p>когда функция сравнения является функцией обратного вызова (как в реализации qsort () libc), быстрая сортировка выполняется медленнее сортировки на 15% при случайном вводе и 30% для уже отсортированного массива для 64-битных целых чисел.</p><p>с другой стороны, если сравнение не является обратным вызовом, мой опыт показывает, что быстрая сортировка превосходит сортировку слиянием до 25%.</p><p>однако если ваш (большой) массив имеет очень мало уникальных значений, сортировка слиянием начинает выигрывать по сравнению с быстрой сортировкой в любом случае.</p><p>поэтому, возможно, суть заключается в следующем: если сравнение стоит дорого (например, функция обратного вызова, сравнение строк, сравнение многих частей структуры, в большинстве случаев переходящих к второй-четвертой части "если", чтобы иметь значение) - есть вероятность, что вы будете лучше с сортировкой слиянием. для более простых задач быстрая сортировка будет быстрее.</p><p>тем не менее все ранее сказанное верно: - быстрая сортировка может быть n ^ 2, но седжвик утверждает, что хорошая рандомизированная реализация имеет больше шансов, что компьютер выполнит сортировку, чтобы быть пораженным молнией, чем n ^ 2 - mergesort требует дополнительного места</p>

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

<p>небольшие дополнения к быстрой сортировке против слияния.</p><p>также это может зависеть от вида сортировки предметов. если доступ к элементам, обмен и сравнение не являются простыми операциями, такими как сравнение целых чисел в плоской памяти, тогда сортировка слиянием может быть предпочтительным алгоритмом.</p><p>например, мы сортируем элементы по сетевому протоколу на удаленном сервере.</p><p>кроме того, в пользовательских контейнерах, таких как "связанный список", быстрая сортировка не дает никаких преимуществ.<br> 1. сортировка слиянием в связанном списке, не требует дополнительной памяти. 2. доступ к элементам в быстрой сортировке не последовательный (в памяти)</p>

<p>трудно сказать. худший из mergesort - это n (log2n) -n + 1, что точно, если n равно 2 ^ k (я уже доказал это). и для любого n это между (n lg n - n +) 1) и (n lg n + n + o (lg n)). но для быстрой сортировки лучше всего использовать nlog2n (также n равно 2 ^ k). если разделить mergesort на quicksort, то она равна единице, когда n бесконечно. как будто худший случай mergesort лучше, чем лучший вариант quicksort, почему мы используем быструю сортировку? но помните, mergesort не на месте, он требует 2n memeroy space. и mergesort также нужно сделать много копий массива, которые мы не включайте в анализ алгоритма. в word mergesort действительно быстрее, чем быстрая сортировка в theroy, но в действительности вам нужно учитывать пространство памяти, стоимость копирования массива, слияние медленнее, чем быстрая сортировка. однажды я сделал эксперимент, в котором мне было дано 1000000 цифр в java классом random, и потребовалось 2610ms для сортировки слиянием, 1370ms для быстрой сортировки.</p>

<p>при прочих равных условиях я бы ожидал, что большинство людей будут использовать все, что наиболее удобно, и это будет qsort (3). кроме этой быстрой сортировки известно, что она очень быстро работает с массивами, точно так же, как сортировка слиянием является распространенным выбором для списков.</p><p>мне интересно, почему так редко можно увидеть <a href="http://en.wikipedia.org/wiki/radix\_sort"><strong> radix </strong></a> или сортировку по сегментам. они o (n), по крайней мере, в связанных списках, и все, что нужно, это какой-то метод преобразования ключа в порядковое число. (строки и поплавки работают просто отлично.)</p><p>я думаю, причина в том, как преподается информатика. мне даже пришлось продемонстрировать моему лектору по анализу алгоритмов, что действительно возможно сортировать быстрее, чем o (n log (n)). (у него было доказательство того, что нельзя <em> сравнивать </em> сортировать быстрее, чем o (n log (n)), что верно.)</p><p>в других новостях числа с плавающей точкой могут быть отсортированы как целые числа, но вы должны повернуть отрицательные числа потом.</p><p>правка: на самом деле, вот еще более порочный способ сортировки чисел с плавающей точкой: <a href="http://www.stereopsis.com/radix.html">http://www.stereopsis.com/radix.html</a> . обратите внимание, что трюк с переключением битов можно использовать независимо от того, какой алгоритм сортировки вы на самом деле используете.</p>

<p>учитывайте сложность времени и пространства. для сортировки слиянием: сложность времени: o(nlogn), сложность пространства: o (nlogn)</p><p>для быстрой сортировки: сложность времени: o (n ^ 2), сложность пространства: o (n)</p><p>теперь они оба выигрывают по одному сценарию каждый. но, используя случайную опору, вы почти всегда можете уменьшить сложность времени быстрой сортировки до o (nlogn).</p><p>таким образом, быстрая сортировка предпочтительна во многих приложениях, а не сортировка слиянием.</p>

<p>быстрая сортировка является алгоритмом сортировки на месте, поэтому она лучше подходит для массивов. с другой стороны, сортировка слиянием требует дополнительного хранения o (n) и больше подходит для связанных списков.</p><p>в отличие от массивов, в список избранного мы можем вставлять элементы посередине с пробелом o(1) и временем o(1), поэтому операция слияния в сортировке слиянием может быть реализована без дополнительное пространство однако выделение и отмена выделения дополнительного пространства для массивов отрицательно влияет на время выполнения сортировки слиянием. сортировка слиянием также поддерживает связанный список, поскольку к данным обращаются последовательно, без особого произвольного доступа к памяти.</p><p>с другой стороны, быстрая сортировка требует большого количества произвольного доступа к памяти, а с помощью массива мы можем напрямую обращаться к памяти без какого-либо обхода, как того требуют связанные списки. кроме того, быстрая сортировка при использовании для массивов имеет хорошее месторасположение, поскольку массивы хранятся в памяти непрерывно.</p><p>несмотря на то что средняя сложность обоих алгоритмов сортировки равна o (nlogn), обычно для обычных задач люди используют массив для хранения, и по этой причине быстрая сортировка должна быть предпочтительным алгоритмом.</p><p>правка: я только что обнаружил, что сортировка слиянием худший/лучший/средний случай всегда nlogn, но быстрая сортировка может варьироваться от n2 (худший случай, когда элементы уже отсортированы) до nlogn (avg/лучший случай, когда сводка всегда делит массив на два половинки).</p>