Daniel's Blog

edit

Merge Sort

Posted by Daniel Lyons Mon, 27 Nov 2006 10:15:00 GMT

Lance is fond of merge sort. I think the extra complexity here indicates that merge sort is basically easier on the human brain but doing the same kind of thing as quick sort, which is easier algorithmically. For some reason.

Anyway, here it is in highly convoluted Erlang. I went ahead and re-implemented the core algorithms for pedagogical purposes.

-module(merge).
-export([merge/2, sort/1, map2/2]).

merge([X|Xs], [Y|Ys]) when X < Y ->
    [ X | merge(Xs, [Y|Ys]) ];
merge([X|Xs], [Y|Ys]) when X > Y ->
    [ Y | merge([X|Xs], Ys) ];
merge(X, []) ->
    X;
merge([], Y) ->
    Y.

That’s a very pattern-oriented merge function. Very easy though.

map2(Fun, [A,B|T]) ->
    [ Fun(A, B) | map2(Fun, T) ];
map2(_, T) ->
    T.

The map2 function is basically going to apply some function against every two items in the list. This would suck to do without pattern matching. I go ahead and just concatenate any single item I find without passing it through the function or discarding it, because another part of my algorithm expects that behavior.

unwrap_or_recur(_, [X]) ->
    X;
unwrap_or_recur(Fun, X) ->
    unwrap_or_recur(Fun, Fun(X)).

OK. This is weird. In particular, this is the kind of thing that just wouldn’t be done in a non-functional language. But it felt natural here.

unwrap_or_recur takes two arguments: a function and a list. If the list only has one thing in it, I return that thing. Otherwise, I recursively invoke unwrap_or_recur, passing the same function through and the list after having applied the function to it. This is weird but it will begin to make sense in a moment, so hold this thought.

sort(X) ->
    unwrap_or_recur(fun(L) -> map2(fun merge/2, L) end, 
                    [ [Item] || Item <- X ]).

How does merge sort work? Well, basically, you consider each item as a queue of itself. Then you merge every two queues into a bigger queue. Repeat until you run out of queues.

Starting with a function that merges two queues, the merge function, I thought, well, I can create a bunch of queues by just making each element a list. That’s the list comprehension in there. Take a look:

18> [ [X] || X <- [7, 3, 1, 5] ].
[[7],[3],[1],[5]]

OK. So then to get the next step, merging those queues, I just need to apply merge on the first and second pairs of queues. It would look like this:

19> merge:merge([7],[3]).
[3,7]
20> merge:merge([1],[5]).
[1,5]

The map2 function basically looks at [[7],[3],[1],[5]] and translates it into this: [Fun([7],[3]), Fun([1],[5])]. That’s going to produce this list: [[3,7], [1,5]]

So the first argument to sort, fun(L) -> map2(fun merge/2, L) end, is a closure that takes a list, and passes every two arguments off to merge. The second argument to sort is the actual list to sort, from the formal parameter.

So what happens in unwrap_or_recur? Well, it just keeps calling the closure above until there’s only one item inside the list. Suppose we do one more recursive application on the list [[3,7], [1,5]], what do we get? This: [[1,3,5,7]]. So then unwrap_or_recur pops the one list item out—the same as dequeuing the entire last queue.

This is all very cool, but I still think I prefer the simplicity of quick sort.