Merge Sort implementation in Erlang

What else can you do in a dull Saturday evening 😉

-module (sorting).
-compile (export_all).

merge_sort([]) -> [];
merge_sort(L) ->
    {L1 , L2} = split(L),
    merge(merge_sort(L1),merge_sort(L2)).

merge(X , Y) ->
     merge(X,Y,[]).

merge([], [] , X) -> X;
merge([] , S2, X) -> X ++ S2;
merge(S1 , [], X) -> X ++ S1;
merge([H1 | T1] , [H2 | T2], X) when H1 >= H2 ->
    merge( [H1 | T1] , T2 , append(X,[H2])); %tail recursion
merge([H1 | T1] , [H2 | T2], X) ->
     merge( T1 , [H2 | T2], append(X,[H1])). %tail recursion 

append(X , Y) ->
      X ++ Y. % appending two list ! how cool!

split(L) ->
    split(L , {[] , []}).

split([] , {X , Y}) -> { X , Y };
split([H|T] , {X , Y}) ->
    split( T , { Y , append(X , [H]) }). %tail recursion

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s