Merge sort (Erlang)

From LiteratePrograms

Other implementations: ACL2 | C | C++ | dc | Eiffel | Erlang | Haskell | Java | JavaScript | Lisp | OCaml | Oz | Perl | Prolog | Python | Ruby | Scheme

This is an implementation of the merge sort algorithm in Erlang, as applied to cons-based lists. The sorting predicate is user-specified; use lte (defined below) to provide the usual stable sorting of numbers.

There are three functions in the implementation. The first, split, is used to chop the list into two pieces, each of which we will later sort recursively:

<<split>>=
split(Ls) ->
    split(Ls, Ls, []).
split([], Ls1, Ls2) ->
    {reverse(Ls2) , Ls1};
split([_], Ls1, Ls2) ->
    {reverse(Ls2) , Ls1};
split([_,_|TT], [Ls1_H | Ls1_T], Ls2) ->
    split(TT, Ls1_T, [Ls1_H | Ls2]).

A more intuitive way of splitting the list might be to put all odd-positioned elements in one sublist, and the rest in another. This, however, is not stable: a list that is already partially-ordered according to the predicate might be rearranged.

For example, given a binary predicate string_length_lte that returns true iff the first argument is not longer than the second, and the list ("aaa" "bbb" "ccc"), you get ("aaa" "ccc" "bbb") back. Thus the trick of having a copy of the list that is consumed two elements at a time, in order to split the list in the middle.

The next, merge, is the heart of the algorithm and operates by interleaving the elements of two ordered lists in such a way that the combined list is ordered. This process takes only linear (O(n)) time:

<<merge>>=
merge(_, [], Ls2) ->
    Ls2;
merge(_, Ls1, []) ->
    Ls1;
merge(Rel, [H1|T1], [H2|T2]) ->
    case Rel(H1, H2) of
	true ->
	    [H1 | merge(Rel, T1, [H2|T2])];
	false ->
	    [H2 | merge(Rel, [H1|T1], T2)]
    end.

Finally, we use these together to implement mergesort, by splitting the list into two pieces, sorting them recursively, and then merging them. We handle the trivial cases by simply returning the list:

<<mergesort.erl>>=
-module(mergesort).
-export(msort/2, msort_lte/1, msort_gte/1).
split
merge
msort(_, []) ->
    [];
msort(_, [H]) ->
    [H];
msort(Rel, Ls) ->
    {Half1 , Half2} = split(Ls),
    merge(Rel, msort(Rel, Half1), msort(Rel, Half2)).
% Parameterize msort with commonly-used predicates
lte(X, Y) ->
    (X < Y) or (X == Y).
gte(X, Y) ->
    (X > Y) or (X == Y).
msort_lte(Ls) ->
    msort(fun lte/2, Ls).
msort_gte(Ls) ->
    msort(fun gte/2,
	  Ls).

Download code