为什么 QuackSort 比 Data.List 的随机列表排序快 2 倍？

Question

我在Haskell上寻找MergeSort到HOVM的规范实现，我找到了这个StackOverflow的答案。在移植该算法时，我意识到一些看起来很傻的东西：该算法有一个"减半"；函数，在递归和合并之前，只使用一半的长度将列表一分为二。所以我想：为什么不更好地利用这个传球，使用一个支点，使每一半分别比那个支点小和大呢？这将增加递归合并调用应用于已排序列表的几率，这可能会加快算法！

我做了这个更改，得到了以下代码：

import Data.List
import Data.Word
randomList :: Word32 -> Word32 -> [Word32]
randomList seed 0    = []
randomList seed size = seed : randomList (seed * 1664525 + 1013904223) (size - 1)
quacksort :: [Word32] -> [Word32]
quacksort []           = []
quacksort [x]          = [x]
quacksort (p : x : xs) = split p (p : x : xs) [] [] where
-- Splits the list in two halves of elements smaller/bigger than a pivot
split p []       as bs = merge (quacksort as) (quacksort bs)
split p (x : xs) as bs = quack p (p < x) x xs as bs
-- Helper function for `split`
quack p False x xs as bs = split p xs (x : as) bs
quack p True  x xs as bs = split p xs as (x : bs)
-- Merges two lists as a sorted one
merge []       ys       = ys
merge xs       []       = xs
merge (x : xs) (y : ys) = place (x < y) x xs y ys
-- Helper function for `merge`
place False x xs y ys = y : merge (x : xs) ys
place True  x xs y ys = x : merge xs (y : ys)
main :: IO ()
main = do
let l = randomList 0 2000000
let b = quacksort l
print $ sum b

然后我对它进行了基准测试，令我惊讶的是，它确实比Haskell的官方Data.List排序快了2倍。所以我想知道为什么在实践中没有使用它，突然间，我意识到了一个显而易见的事实：合并排序在已经排序的列表上并没有表现得更好。哦。所以庸医背后的全部假设都失败了。不仅如此，对于反向排序的列表，它的表现会很糟糕，因为它无法产生大小相似的两半(除非我们能猜到一个非常好的枢轴(。所以，庸医在任何情况下都是古怪的，不应该在实践中使用。但是，那么。。。

为什么它的执行速度比Data快2倍。List对随机列表的排序

我想不出有什么好的理由会这样。使每一半小于/大于一个枢轴不会改变必须调用合并调用的次数，因此不应该有任何积极影响。但将其恢复为传统的合并确实会使速度慢2倍，因此，出于某种原因，有序拆分会有所帮助。

Answer 1

您的split将列表拆分为两个有序的半部分，因此merge首先消耗其第一个参数，然后只生成完整的后半部分。换句话说，它相当于++，在总是True的前半部分进行冗余比较。

在真正的合并中，合并实际上在随机数据上做了两倍的工作，因为这两个部分没有排序。

split在分区上花费了一些工作，而在线自下而上的合并则根本不会在那里花费任何工作。但是内置的排序试图检测输入中的有序运行，显然额外的工作是不可忽略的。