the way merge-sort faster than insertion-sort puzzles me

Question

Just got my feet wet in sorting algorithm with Haskell. I've implemented insertion-sort and 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

Here's how I compared their efficiency:

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

Both of them starts to print out results after a short delay but merge-sort prints much faster. As we know, merge-sort is much faster than insertion-sort for large data sets. I thought that would be shown by how they give results (like a long delay versus a short one) not how they print results. Is it because I use foldr in insertion-sort? What's behind the scene?

EDIT: Thx guys. I've heard about lazy evaluation since I started to learn Haskell but yet got the hang of it. Would anybody illustrate a bit more with a small data set, say [5,2,6,3,1,4]? How is it possible to output results before finish sorting with foldr since the first elements comes at last?

Answer 1

Behind the scene is lazy evaluation. The start of the sorted lists is determined before the sort is complete, so it can be output before the work is finished. Since a mergesort is faster, the merge-sorted list is printed out faster.

As requested: how sorting [5,2,6,3,1,4] proceeds. I use insert_sort = foldr ins [] for brevity.

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

And merge sort (abbreviations: 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

Admittedly I've taken a few short cuts, but Haskell isn't the only lazy one.

Answer 2

OK here's the break down. You want me to print out:

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

I happen to know that this is a list. So First I'll print out an open brace

[

Then I'll look for the first element of the list, print that out, and then a comma. That means I have to start evaluating that expression until I can figure out what the first element of the list is.

merge_sort THUNK0

Well now I need to pattern match. Either THUNK matches (x:[]) or it doesn't. But I don't know yet. So I'll evaluate that thunk a bit. I make that thunk produce the first two random numbers (out of 100000). Now I know that it doesn't match the first definition, so I take the second definition of merge_sort.

merge_sort keys = merge THUNK1 THUNK2 -- keys = THUNK0

Well that's easy enough...it's just a call to merge. I'll expand that definition. Oh crap, there are three different patterns this might match. I guess I should evaluate THUNK1 a little and see if it matches the first definition's pattern, (x:xs)

merge_sort (take THUNK3 THUNK0)

Back to merge_sort again, are we? That means I need to evaluate (take THUNK3 THUNK0) just enough to tell if it matches (x:[]) or not. Oh CRAP. take is strict in its first argument...that means I have to fully evaluate THUNK3. Ok...deep breaths...

len = length THUNK0 `div` 2

Now here's an irritating case. To calculate length on THUNK0 (which is a list), I have to expand the WHOLE SPINE. I don't have to actually calculate the values inside, but I do need to flesh out the structure of the entire list. This, of course, is done one pattern match at a time, determining whether it is [], or (x:xs). But as a whole, length is "spine strict".

short pause whilst I flesh out the spine of a 100000-element list

Phew, got that done. Now I know the length, which means I know len = 500000. THUNK0 is finally fully evaluated! Phew! Where was I?

merge_sort (take 500000 THUNK3)

---

And so forth. merge_sort will continue trying to be as lazy as possible. Recursive calls to merge_sort will be as lazy as possible. Eventually, to determine the very first element of the outermost merge_sort, we will need to know the very first element of both recursive calls to merge_sort. And to know the first element of those...we'll need the first element of subsequent recursive calls, etc. So there will be about O(n) work done, because every element needs to be evaluated (performing the random number generation for each one).

Then, think of it like a tournament. Each element is paired up against another element. The "winning" (lowest) elements move on to the next round (becoming the first element of the recursive call to the lowest merge_sorts). There is another competition with 1/2 as many combatants, and 1/2 of those (1/4 of the total) move on to the next round, etc. This also turns out to be O(n) work, since the (n/2) comparisons are performed during the first round, and subsequent rounds grow smaller much too quickly to be significant. (The sum 1/2 + 1/4 + 1/8 ... converges at 1, meaning a total of n comparisons are performed.)

All in all, O(n) work needs to be performed in order to finally produce the first element. Additional work needs to be performed for subsequent elements, but the total amount of work ends up being O(n log(n)).

---

Now contrast this with insert_sort. It too produces the first element in O(n) time, but the total amount of work is O(n²) in the worst case: it "inserts" the list's elements into the sorted list one by one, and traverses this sorted list potentially to its very end each time.