-module(mergesort).
-export([sort/1]).
 
% Usage: 
% c(mergesort).
%
% mergesort:sort([2,7,55,4,30,6,7,99,1,100]).
% => [1,2,4,6,7,7,30,55,99,100]
 
sort([]) -> [];
sort([L]) -> [L];
sort(List) -> 
    Middle = length(List) div 2,
    {Left, Right} = lists:split(Middle, List),
    merge(sort(Left),sort(Right)).
 
merge(Left, Right) -> merge(Left, Right, []).
 
merge([L|Left], [R|Right], Acc) when L < R -> 
    merge(Left, [R|Right], [L|Acc]);
merge(Left, [R|Right], Acc) -> 
    merge(Left, Right, [R|Acc]);
merge([L|Left], [], Acc) -> 
    merge(Left, [], [L|Acc]);
merge([], [R|Right], Acc) -> 
    merge([], Right, [R|Acc]);
merge([], [], Acc) -> lists:reverse(Acc).
 
% From a comment by Per Gustafsson
% http://jchris.mfdz.com/life/2008/8/erlang_mergesort#comments
 
% In this case I think it is actually better to not use a tail 
% recursive definition of merge. I am pretty sure that this is 
% more efficient:
 
% (Note from jchris) I'm not sure what impact this will have 
% on memory requirements.
 
merge(Left, []) -> Left;
merge([], Right) -> Right;
merge([L|Left], [R|_] = Right) when L < R ->
    [L | merge(Left, Right)];
merge(Left, [R|Right], Acc) ->
    [R | merge(Left, Right)].
 
% If you still want a tail recursive version it should probably 
% look something like this:
 
merge(Left, [], Acc) -> lists:reverse(Acc, Left);
merge([], Right, Acc) -> lists:reverse(Acc, Right);
merge([L|Left], [R|_] = Right) when L < R ->
    merge(Left, Right, [L|Acc]);
merge(Left, [R|Right], Acc) ->
    merge(Left, Right, [R|Acc]).
 
% lists:reverse(List, Tail) is equivalent to 
% lists:reverse(List) ++ Tail but is more efficient.
 
 
% The Wikipedia version
% from http://en.wikipedia.org/wiki/Merge_sort
 
% function mergesort(m)
%     var list left, right, result
%     if length(m) ≤ 1
%         return m
% 
%     var middle = length(m) / 2
%     for each x in m up to middle
%          add x to left
%     for each x in m after middle
%          add x to right
%     left = mergesort(left)
%     right = mergesort(right)
%     result = merge(left, right)
%     return result
% 
% function merge(left,right)
%     var list result
%     while length(left) > 0 and length(right) > 0
%         if first(left) ≤ first(right)
%             append first(left) to result
%             left = rest(left)
%         else
%             append first(right) to result
%             right = rest(right)
%     end while
%     if length(left) > 0 
%         append rest(left) to result
%     if length(right) > 0 
%         append rest(right) to result
%     return result