合并排序的方式比插入排序更快谜题

Question

刚刚在排序算法与Haskell湿了我的脚。我实现了插入排序和合并排序

insert_sort :: (Ord a, Show a) => [a] -> [a] 
insert_sort keys = foldr f [] keys 
      where f key []  = [key] 
       f key acc  = insert key acc 
       insert y []  = [y] 
       insert y (x:xs) 
        | x < y  = x : insert y xs 
        | otherwise = y : x : xs 

merge_sort :: (Ord a, Show a) => [a] -> [a] 
merge_sort (x:[]) = [x] 
merge_sort keys = merge (merge_sort (take len keys)) (merge_sort (drop len keys)) 
     where len   = length keys `div` 2 
      merge :: [a] -> [a] -> [a] 
      merge (x:xs) []  = (x:xs) 
      merge []  (y:ys) = (y:ys) 
      merge (x:xs) (y:ys) = if x <= y 
            then x : merge (xs) (y:ys) 
            else y : merge (x:xs) ys 

以下是我比较了它们的效率：

insert_sort $ take 100000 $ randomRs (1,100000) $ mkStdGen 1 ::[Int] 
merge_sort $ take 100000 $ randomRs (1,100000) $ mkStdGen 1 ::[Int] 

他们都开始多在短暂的延迟后，打印出结果，但合并排序打印更快。我们知道，合并排序比大数据集的插入排序快得多。我认为这将表现在他们如何给出结果（如长时间延迟与短时延迟），而不是他们如何输出结果。是因为我使用foldr进行插入排序吗？现场背后是什么？

编辑：Thx guys。自从我开始学习Haskell以来，我听说过懒惰的评估，但还没有掌握它。有人会用一个小数据集说明一点，比如[5,2,6,3,1,4]？自从第一个元素终于出现以后，如何在使用foldr完成排序之前输出结果？

Answer 1

幕后的是懒惰的评价。在排序完成之前确定排序列表的开始，因此可以在工作完成之前输出。由于合并速度更快，因此合并排序列表的打印速度更快。

按要求：如何排序[5,2,6,3,1,4]收益。为简洁起见，我使用insert_sort = foldr ins []。

insert_sort [5,2,6,3,1,4] 
    = foldr ins [] [5,2,6,3,1,4] 
    = 5 `ins` foldr ins [] [2,6,3,1,4] 
    = 5 `ins` 2 `ins` [6,3,1,4] ... 
    = 5 `ins` 2 `ins` 6 `ins` 3 `ins` 1 `ins` 4 `ins` [] 
    = 5 `ins` 2 `ins` 6 `ins` 3 `ins` 1 `ins` (4:[]) 
    = 5 `ins` 2 `ins` 6 `ins` 3 `ins` (1:4:[]) 
    = 5 `ins` 2 `ins` 6 `ins` (1 : (3 `ins` (4:[]))) 
    = 5 `ins` 2 `ins` (1 : (6 `ins` (3 `ins` (4:[])))) 
    = 5 `ins` (1 : (2 `ins` (6 `ins` (3 `ins` (4:[]))))) 
    = 1 : (5 `ins` (2 `ins` (6 `ins` (3 `ins` (4:[]))))) -- now 1 can be output 
    = 1 : (5 `ins` (2 `ins` (6 `ins` (3:4:[])))) 
    = 1 : (5 `ins` (2 `ins` (3 : (6 `ins` (4:[]))))) 
    = 1 : (5 `ins` (2 : (3 : (6 `ins` (4:[]))))) 
    = 1 : 2 : (5 `ins` (3 : (6 `ins` (4:[]))))   -- now 2 can be output 
    = 1 : 2 : 3 : (5 `ins` (6 `ins` (4:[])))    -- now 3 
    = 1 : 2 : 3 : (5 `ins` (4:6:[])) 
    = 1 : 2 : 3 : 4 : (5 `ins` (6:[]))     -- now 4 
    = 1 : 2 : 3 : 4 : 5 : 6 : []       -- done 

和排序合并（缩写：merge = mg，merge_sort = ms）：

merge_sort [5,2,6,3,1,4] 
    = mg (ms [5,2,6]) (ms [3,1,4]) 
    = mg (mg (ms [5]) (ms [2,6])) (mg (ms [3]) (ms [1,4])) 
    = mg (mg [5] (mg [2] [6])) (mg [3] (mg [1] [4])) 
    = mg (mg [5] [2,6]) (mg [3] [1,4]) 
    = mg (2 : mg [5] [6]) (1 : mg [3] [4]) 
    = 1 : mg (2 : mg [5] [6]) (mg [3] [4])    -- now 1 can be output 
    = 1 : mg (2 : mg [5] [6]) [3,4] 
    = 1 : 2 : mg (mg [5] [6]) [3,4]      -- now 2 can be output 
    = 1 : 2 : mg [5,6] [3,4] 
    = 1 : 2 : 3 : mg [5,6] [4]       -- now 3 
    = 1 : 2 : 3 : 4 : mg [5,6] []       -- now 4 
    = 1 : 2 : 3 : 4 : 5 : 6 : []       -- now 5 and 6 

诚然，我已经采取了一些捷径，但Haskell是不是只有懒之一。

Answer 2

确定这里是分解。你要我打印出来：

merge_sort $ take 100000 $ randomRs (1,100000) $ mkStdGen 1 ::[Int] 

我碰巧知道这是一个列表。所以，首先我会打印出一个开放的括号

[ 

然后我会寻找列表的第一个元素，即打印出来，然后一个逗号。这意味着我必须开始评估该表达式，直到我能够确定列表的第一个元素是什么。

merge_sort THUNK0 

那么现在我需要模式匹配。 THUNK匹配(x:[])或者它不。但我还不知道。所以我会评估一下这个thunk。我让这个thunk产生前两个随机数（100000）。现在我知道它不符合第一个定义，所以我拿第二个定义merge_sort。

merge_sort keys = merge THUNK1 THUNK2 -- keys = THUNK0 

那么这很容易......这只是一个调用合并。我会扩展这个定义。哦，废话，有三个这可能匹配不同的模式。我想我应该评估THUNK1一点，看看它是否第一个定义的模式相匹配，(x:xs)

merge_sort (take THUNK3 THUNK0) 

回到merge_sort再次，我们是什么？这意味着我需要评估(take THUNK3 THUNK0)就足以说明它是否与(x:[])匹配。哦，CRAP。 take是严格在其第一个参数...这意味着我必须完全评估 THUNK3。好吧......深呼吸......

len = length THUNK0 `div` 2 

现在，这里是一个令人烦恼的案例。要计算THUNK0（这是一个列表）上的length，我必须展开整个SPOLE。我不必实际计算里面的值，但是我需要充实整个列表的结构。当然，这是一次完成一个模式匹配，确定它是否是[]或(x:xs)。但总体来说，length是“脊椎严格”。

短暂的停顿，而我割肉出局100000元素列表

唷脊柱，得到了实现。现在我知道长度，这意味着我知道len = 500000。 THUNK0是终于充分评估！唷！我在哪里？

merge_sort (take 500000 THUNK3) 

---

等等。 merge_sort将继续尽可能地变得懒惰。对merge_sort的递归调用将尽可能慢。最终，为了确定最外面的第一个元素merge_sort，我们需要知道递归调用merge_sort的第一个元素。并且要知道这些元素的第一个元素...我们需要后续递归调用的第一个元素等。因此，将会有大约O（n）工作完成，因为每个元素都需要进行评估（执行随机为每一个号码生成）。

然后，把它想象成一个比赛。每个元素都与另一个元素配对。 “获胜”（最低）元素移动到下一轮（成为递归调用的最低元素，即merge_sort s）。还有另外一场比赛的战斗人员数量是1/2，而那些人的（总数的1/4）移动到下一轮，等等。这也证明是O（n）工作，因为（n/2）比较是在第一轮中进行的，随后的回合变得太快而太快而不重要。 （总和1/2 + 1/4 + 1/8 ...收敛于1，这意味着执行总共n次比较。）

总而言之，O（n）工作需要执行以便最终产生第一个元素。需要为后续元素执行额外工作，但总工作量为O（n log（n））。

---

现在将其与insert_sort对比。试想一下它是如何工作的：它遍历列表，并将每个元素“插入”到一个排序列表中。这意味着你不能确定知道排序的第一个元素是，直到你执行了最后一项工作，并且将最后一个元素（可能是最低的）插入到排序列表中。

我希望这清楚地说明了merge_sort如何并不需要执行所有的工作，以便开始生产结果，而insert_sort一样。