то, как merge-sort быстрее insertion-sort, озадачивает меня

Только что намочил ноги в алгоритме сортировки на Haskell. Я реализовал insertion-sort и merge-sort

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]

Оба они начинают выводить результаты после небольшой задержки, но merge-sort печатает намного быстрее. Как мы знаем, merge-sort намного быстрее insertion-sort для больших наборов данных. Я думал, что это будет видно по тому, как они выдают результаты (например, длинная задержка против короткой), а не по тому, как они печатают результаты. Это потому, что я использую foldr в insertion-sort? Что за сценой?

EDIT: Спасибо, ребята. Я слышал о ленивой оценке с тех пор, как начал изучать Haskell, но так и не понял, что это такое. Не мог бы кто-нибудь проиллюстрировать немного больше на небольшом наборе данных, скажем [5,2,6,3,1,4]? Как можно вывести результаты до окончания сортировки с помощью foldr, ведь первые элементы приходят последними?