Я думаю, что ответ @comingstorm находится в значительной степени на носу, но здесь является еще некоторой информацией об истории функции вида GHC.

В исходном коде для Data.OldList, можно найти реализация из sort и проверить для себя, что это - сортировка слиянием. Чуть ниже определения в том файле следующий комментарий:

Quicksort replaced by mergesort, 14/5/2002.

From: Ian Lynagh <igloo@earth.li>

I am curious as to why the List.sort implementation in GHC is a
quicksort algorithm rather than an algorithm that guarantees n log n
time in the worst case? I have attached a mergesort implementation along
with a few scripts to time it's performance...

Так, первоначально функциональный quicksort использовался (и функция qsort все еще там, но прокомментированный). Сравнительные тесты Ian показали, что его сортировка с объединением была конкурентоспособна по отношению к quicksort в "случайном списке" случай и в широком масштабе превзошла его по характеристикам в случае уже отсортированных данных. Позже, версия Ian была заменена другой реализацией, которая была приблизительно вдвое более быстрой, согласно дополнительным комментариям в том файле.

основной вопрос с оригиналом qsort был то, что он не использовал случайный центр. Вместо этого это вертелось вокруг первого значения в списке. Это очевидно довольно плохо, потому что это подразумевает, что производительность будет худшим случаем (или близко) для отсортированного (или почти отсортированный) вход. К сожалению, существует несколько проблем в переключении с "центра на первом" к альтернативе (или случайны, или - как в Вашей реализации - где-нибудь в "середине"). На функциональном языке без побочных эффектов, управляя псевдослучайным входом определенная проблема, но скажем, Вы решаете это (возможно, путем встраивания генератора случайных чисел в функцию вида). У Вас все еще есть проблема, которая, при сортировке неизменного связанного списка, определении местоположения произвольного центра и затем разделении на основе его включит несколько обходов списка и подперечислит копии.

я думаю единственный способ понять, что воображаемые преимущества quicksort состояли бы в том, чтобы написать список к вектору, отсортировать его на месте (и устойчивость вида жертвы) и записать его обратно к списку. Я не вижу, что это могло когда-либо быть полной победой. С другой стороны, если бы у Вас уже есть данные в векторе, затем оперативный quicksort определенно был бы разумной опцией.

В отдельно-связанном-списке сортировка с объединением может быть сделана на месте. Кроме того, наивные реализации сканируют более чем половину списка для получения запуска второго подсписка, но запуск второго подсписка выпадает как побочный эффект сортировки первого подсписка и не нуждается в дополнительном сканировании. Одна вещь quicksort имеет переходящий через сортировку с объединением, когерентность кэш-памяти. Quicksort работает с элементами друг близко к другу в памяти. Как только элемент косвенности вводит в него, как то, когда Вы сортируете массивы указателей вместо самих данных, то преимущество становится меньше.

Сортировка с объединением имеет трудные гарантии поведения худшего случая, и легко сделать стабильную сортировку с ним.

Короткий ответ:

Quicksort выгоден для массивов (оперативный, быстро, но не оптимальный худший случай). Сортировка с объединением для связанных списков (быстро, худший случай, оптимальный, стабильный, простой).

Quicksort является медленным для списков, Сортировка с объединением не существует для массивов.

Много аргументов на том, почему Quicksort не используется в Haskell, кажутся вероятными. Однако, по крайней мере, Quicksort не медленнее, чем Сортировка с объединением для случайного случая. На основе реализации, данной в книге Richard Bird, Взгляды Функционально в Haskell, я сделал Quicksort с 3 путями:

tqsort [] = []
tqsort (x:xs) = sortp xs [] [x] [] 
  where
    sortp [] us ws vs     = tqsort us ++ ws ++ tqsort vs
    sortp (y:ys) us ws vs =
      case compare y x of 
        LT -> sortp ys (y:us) ws vs 
        GT -> sortp ys us ws (y:vs)
        _  -> sortp ys us (y:ws) vs

я сравнил нескольких случаев, например, списки размера 10^4 содержащий Интервал между 0 и 10^3 или 10^4, и так далее. Результатом является Quicksort с 3 путями, или даже версия Bird лучше, чем Сортировка с объединением GHC, что-то как 1.x~3.x быстрее, чем Сортировка с объединением ghc, в зависимости от типа данных (много повторений? очень редкий?). Следующая статистика сгенерирована критерий :

benchmarking Data.List.sort/Diverse/10^5
time                 223.0 ms   (217.0 ms .. 228.8 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 226.4 ms   (224.5 ms .. 228.3 ms)
std dev              2.591 ms   (1.824 ms .. 3.354 ms)
variance introduced by outliers: 14% (moderately inflated)

benchmarking 3-way Quicksort/Diverse/10^5
time                 91.45 ms   (86.13 ms .. 98.14 ms)
                     0.996 R²   (0.993 R² .. 0.999 R²)
mean                 96.65 ms   (94.48 ms .. 98.91 ms)
std dev              3.665 ms   (2.775 ms .. 4.554 ms)

Однако существует другое требование sort указано в Haskell 98 / 2010 : это должно быть стабильно . Типичная реализация Quicksort с помощью Data.List.partition стабильна , но выше каждый не.

Более позднее дополнение : стабильный Quicksort с 3 путями, упомянутый в комментарии, кажется с такой скоростью, как tqsort здесь.

Я не уверен, но рассмотрение кода, я не думаю Data.List.sort, Сортировка с объединением, поскольку мы знаем это. Это просто делает единственную передачу, запускающуюся с эти sequences функция красивым треугольным взаимным рекурсивным способом с ascending и descending функции для приведения к списку уже возрастания или убывающих заказанных блоков в необходимом порядке. Только затем это начинает объединяться.

Это - проявление поэзии в кодировании. В отличие от Quicksort, его худший случай (общий случайный вход) имеет O (nlogn) временная сложность, и лучший случай (уже отсортированное возрастание или убывание) является O (n).

я не думаю, что любой другой алгоритм сортировки может разбить его.