为什么 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.List 对随机列表的排序快 2 倍？

我想不出出现这种情况的充分理由。使每一半都比枢轴更小/更大不会改变必须调用合并调用的次数，因此它不应该产生任何积极的效果。但是将其恢复为传统的合并排序确实会使速度慢 2 倍，因此，出于某种原因，有序拆分会有所帮助。

Answer 1

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

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

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