编辑：
事实证明，慢版本实际上是插入排序 O(n^2) 而不是合并排序 O(n log n) 来解释性能问题。我想我可以让未来的读者免于费力通过代码来发现这个答案的痛苦。
原创从这里开始-------------------------------------------
我在 haskell 中编写了两个版本的合并排序，但我无法理解为什么一个版本比另一个版本快 1000 倍。在这两种情况下，我们首先将列表中的项目排序为一个列表，创建一个列表列表。然后我们将列表配对并合并它们，直到只剩下一个列表。问题似乎是我在慢版本中调用“doMerge（x1：x2：xs）= doMerge $ merge x1 x2：doMerge xs”，但在快速版本中调用doMerge（mergePairs xs）。1000倍的速度差异让我感到惊讶！
-- Better version: takes 0.34 seconds to sort a 100,000 integer list.
betMergeSort :: [Int] -> [Int]
betMergeSort list = doMerge $ map (\x -> [x]) list
where
doMerge :: [[Int]] -> [Int]
doMerge [] = []
doMerge [xs] = xs
doMerge xs = doMerge (mergePairs xs)
mergePairs :: [[Int]] -> [[Int]]
mergePairs (x1:x2:xs) = merge x1 x2 : mergePairs xs
mergePairs xs = xs
-- expects two sorted lists and returns one sorted list.
merge :: [Int] -> [Int] -> [Int]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) = if x <= y
then x : merge xs (y:ys)
else y : merge (x:xs) ys
-- Slow version: takes 350 seconds to sort a 100,000 integer list.
slowMergeSort :: [Int] -> [Int]
slowMergeSort list = head $ doMerge $ map (\x -> [x]) list
where
doMerge :: [[Int]] -> [[Int]]
doMerge [] = []
doMerge (oneList:[]) = [oneList]
doMerge (x1:x2:xs) = doMerge $ merge x1 x2 : doMerge xs
-- expects two sorted list and returns one sorted list.
merge :: [Int] -> [Int] -> [Int]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) = if x <= y then x : merge xs (y:ys) else y : merge (x:xs) ys
查看分析器输出，很明显慢版本正在分配更多内存。我不确定为什么。这两个版本在我的脑海中似乎很相似。有人可以解释为什么分配如此不同吗？
slowMergeSort 分析结果：
Wed Aug 21 12:24 2013 Time and Allocation Profiling Report (Final)
mergeSort +RTS -sstderr -p -RTS s
total time = 12.02 secs (12017 ticks @ 1000 us, 1 processor)
total alloc = 17,222,571,672 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
slowMergeSort.merge Main 99.2 99.4
individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc
MAIN MAIN 74 0 0.0 0.0 100.0 100.0
main Main 149 0 0.0 0.0 100.0 100.0
main.sortedL Main 165 1 0.0 0.0 99.3 99.5
slowMergeSort Main 167 1 0.0 0.0 99.3 99.5
slowMergeSort.\ Main 170 40000 0.0 0.0 0.0 0.0
slowMergeSort.doMerge Main 168 79999 0.0 0.0 99.2 99.5
slowMergeSort.merge Main 169 267588870 99.2 99.4 99.2 99.4
main.sortVersion Main 161 1 0.0 0.0 0.0 0.0
randomInts Main 151 1 0.0 0.0 0.7 0.5
force Main 155 1 0.0 0.0 0.0 0.0
force.go Main 156 40001 0.0 0.0 0.0 0.0
randomInts.result Main 152 1 0.7 0.5 0.7 0.5
libMergeSort 分析
Wed Aug 21 12:23 2013 Time and Allocation Profiling Report (Final)
mergeSort +RTS -sstderr -p -RTS l
total time = 0.12 secs (124 ticks @ 1000 us, 1 processor)
total alloc = 139,965,768 bytes (excludes profiling overheads)
COST CENTRE MODULE %time %alloc
randomInts.result Main 66.9 64.0
libMergeSort.merge Main 24.2 30.4
main Main 4.0 0.0
libMergeSort Main 2.4 3.2
libMergeSort.merge_pairs Main 1.6 2.3
individual inherited
COST CENTRE MODULE no. entries %time %alloc %time %alloc
MAIN MAIN 74 0 0.0 0.0 100.0 100.0
main Main 149 0 4.0 0.0 100.0 100.0
main.sortedL Main 165 1 0.0 0.0 28.2 35.9
libMergeSort Main 167 1 2.4 3.2 28.2 35.9
libMergeSort.\ Main 171 40000 0.0 0.0 0.0 0.0
libMergeSort.libMergeSort' Main 168 17 0.0 0.0 25.8 32.7
libMergeSort.merge_pairs Main 169 40015 1.6 2.3 25.8 32.7
libMergeSort.merge Main 170 614711 24.2 30.4 24.2 30.4
main.sortVersion Main 161 1 0.0 0.0 0.0 0.0
randomInts Main 151 1 0.0 0.0 67.7 64.0
force Main 155 1 0.0 0.0 0.8 0.0
force.go Main 156 40001 0.8 0.0 0.8 0.0
randomInts.result Main 152 1 66.9 64.0 66.9 64.0