为何在（近乎）有序数据上我的插入排序慢于库归并排序？

兄弟，我太懂这种落差感了——本来以为近乎有序的数据集是插入排序的主场，结果被标准库的sort按在地上摩擦，性能差了十倍不说，内存还飙到离谱。咱们来拆解下问题出在哪：

• 插入排序的理论复杂度陷阱：你可能记得插入排序在近乎有序时是O(n)，但那是命令式数组场景下的结论！Haskell的列表是单链表，插入排序的每一步插入都要遍历到目标位置才能创建新链表节点。像[0..1000000]这种完全有序的列表，每个元素都要遍历到链表末尾才能插入，总操作数是1+2+...+n = n(n+1)/2，这本质是O(n²)的复杂度！而标准库的归并排序是稳定的O(n log n)，log₂(1e6)大概是20，总操作数差了好几个数量级，性能自然天差地别。

• 链表结构的内存开销爆炸：Haskell的单链表每个节点都包含值和指向下一个节点的指针，插入排序在构建结果时会不断创建新的链表片段，纯函数特性又导致旧的链表节点无法被即时回收（直到GC触发）。这就导致内存里同时存在大量中间链表节点，直接把内存占用拉到13GB。而标准库的sort经过高度优化，内部会用更紧凑的数据结构，甚至在-O2下会通过列表融合避免创建完整的中间链表，内存占用自然被压到1.2GB。

• 标准库的黑科技级优化：Data.List.sort可不是普通的归并排序，GHC团队给它堆了超多优化：

  • 小数据集自动切换到插入排序（利用小数据场景下的低常数优势），大数据集用归并排序
  • -O2优化下会启用列表融合，把sort和length这类操作融合成单次遍历，根本不需要构建完整的排序链表，直接计算结果
  • 内部用了高效的分治策略，甚至用非递归实现减少栈开销，还做了内存块复用，极大降低GC压力

• 你的插入排序可能没适配Haskell的优化规则：你说开启-O2后速度翻倍，但标准库的sort在-O2下的优化幅度要大得多。比如如果你的mySort是典型的递归实现：

  mySort :: Ord a => [a] -> [a]
  mySort [] = []
  mySort (x:xs) = insert x (mySort xs)
    where
      insert x [] = [x]
      insert x (y:ys)
        | x <= y    = x : y : ys
        | otherwise = y : insert x ys
  

  这种写法很难被GHC做列表融合，必须先构建完整的排序链表才能计算length，额外多了一次遍历不说，还占用了巨量内存。而标准库的sort和length融合后，全程不需要存储完整链表，内存占用和耗时自然都低。

给你的小建议 #

• 如果要处理近乎有序的大数据集，别用链表试试数组/向量（比如Data.Vector），命令式的原地插入排序在数组上才是真·O(n)，Haskell里也能通过ST monad实现高效的原地操作
• 要是坚持用列表，试试优化插入逻辑，但说实话，面对1e6级别的数据，手写排序很难打过标准库
• 相信标准库！它经过了无数场景的测试和优化，大数据场景下几乎不可能被简单手写排序打败

内容的提问来源于stack exchange，提问作者rjpj1998