performance - 为什么 Haskell 使用归并排序而不是快速排序？

Question

在 Wikibooks' Haskell ，有the following claim :

Data.List offers a sort function for sorting lists. It does not use quicksort; rather, it uses an efficient implementation of an algorithm called mergesort.

Haskell 使用归并排序而不是快速排序的根本原因是什么？ 快速排序通常具有更好的实际性能，但在本例中可能并非如此。我认为快速排序的就地优势很难(不可能？)用 Haskell 列表来实现。

有a related question on softwareengineering.SE ，但这并不是真正关于为什么使用合并排序的问题。

我自己实现了这两种类型来进行分析。合并排序非常优越(对于 2^20 个元素的列表来说，速度大约是其两倍)，但我不确定我的快速排序实现是否是最佳的。

编辑:以下是我的合并排序和快速排序的实现:

mergesort :: Ord a => [a] -> [a]
mergesort [] = []
mergesort [x] = [x]
mergesort l = merge (mergesort left) (mergesort right)
    where size = div (length l) 2
          (left, right) = splitAt size l

merge :: Ord a => [a] -> [a] -> [a]
merge ls [] = ls
merge [] vs = vs
merge first@(l:ls) second@(v:vs)
    | l < v = l : merge ls second
    | otherwise = v : merge first vs

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort [x] = [x]
quicksort l = quicksort less ++ pivot:(quicksort greater)
    where pivotIndex = div (length l) 2
          pivot = l !! pivotIndex
          [less, greater] = foldl addElem [[], []] $ enumerate l
          addElem [less, greater] (index, elem)
            | index == pivotIndex = [less, greater]
            | elem < pivot = [elem:less, greater]
            | otherwise = [less, elem:greater]

enumerate :: [a] -> [(Int, a)]
enumerate = zip [0..]

编辑2 3:我被要求提供我的实现与Data.List中的排序的计时。按照@Will Ness的建议，我编译了this gist使用 -O2 标志，每次更改 main 中提供的排序，并使用 +RTS -s 执行它。排序后的列表是一个廉价创建的伪随机 [Int] 列表，包含 2^20 个元素。结果如下:

• Data.List.sort:0.171s
• mergesort:1.092s(比 Data.List.sort 慢约 6 倍)
• quicksort:1.152s(比 Data.List.sort 慢约 7 倍)

Answer 1

在命令式语言中，快速排序是通过改变数组来就地执行的。正如您在代码示例中演示的那样，您可以通过构建单链表来使快速排序适应像 Haskell 这样的纯函数语言，但这并不那么快。

另一方面，合并排序不是就地算法:简单的命令式实现将合并的数据复制到不同的分配。这更适合 Haskell，它本质上无论如何都必须复制数据。

让我们退后一步:快速排序的性能优势是“传说”——几十年前在与我们今天使用的机器截然不同的机器上建立的声誉。即使您使用相同的语言，这种知识也需要不时地重新检查，因为实际情况可能会发生变化。我读到的关于这个主题的最后一篇基准测试论文中，快速排序仍然名列前茅，但它相对于合并排序的领先优势很小，即使在 C/C++ 中也是如此。

归并排序还有其他优点:它不需要进行调整来避免快速排序的 O(n^2) 最坏情况，而且它自然稳定。因此，如果由于其他因素而失去了狭窄的性能差异，合并排序是一个明显的选择。