merge_sort.erl

-module(merge_sort).

-compile(export_all).

merge_sort([]) ->
    [];
merge_sort([ X | [] ]) ->
    [X];
merge_sort(List) ->
    {FList, SList} = lists:split(erlang:round(erlang:length(List)/2), List),
    lists_merge(merge_sort(FList), merge_sort(SList)).

merge_sort2([]) ->
    [];
merge_sort2([ X | [] ]) ->
    [X];
merge_sort2(List) ->
    {FList, SList} = lists:split(erlang:round(erlang:length(List)/2), List),
    lists_merge2(merge_sort2(FList), merge_sort2(SList)).

lists_merge([] = _L1, L2) ->
    L2;
lists_merge(L1, [] = _L2) ->
    L1;
lists_merge([H1 | T1], [H2 | _] = L2) when H1 =< H2 ->
    [H1] ++ lists_merge(T1, L2);
lists_merge(L1, [H2 | T2]) ->
    [H2] ++ lists_merge(L1, T2).

lists_merge2(L1, L2) ->
    lists_merge_do(lists:reverse(L1), lists:reverse(L2), []).
lists_merge_do([], L2, Tmp) ->
    lists:reverse(L2) ++ Tmp;
lists_merge_do(L1, [], Tmp) ->
    lists:reverse(L1) ++ Tmp;
lists_merge_do([H1 | T1], [H2 | _] = L2, Tmp) when H1 >= H2 ->
    lists_merge_do(T1, L2, [H1 | Tmp]);
lists_merge_do(L1, [H2 | T2], Tmp) ->
    lists_merge_do(L1, T2, [H2 | Tmp]).

test

L = [X || X <- [random:uniform(10000) || _ <- lists:seq(1, 1000)]].
F1 = fun() -> [sort:merge_sort(L) || _ <- lists:seq(1, 10000)] end. 
F2 = fun() -> [sort:merge_sort2(L) || _ <- lists:seq(1, 10000)] end.
f(T1), {T1, _} = timer:tc(F1), T1/10000.
f(T2), {T2, _} = timer:tc(F2), T2/10000.