Tail recursive mergesort algorithm

Question

I've implemented a recursive mergesort algorithm:

-module(ms).
-import(lists,[sublist/3,delete/2,min/1,reverse/1]).
-export([mergesort/1]).

mergesort([])->
    [];
mergesort([N])->
    N;
mergesort(L)->
    mergesort(split(1,L),split(2,L),[]).

mergesort(L1,L2,[])->
    case {sorted(L1),sorted(L2)} of
    {true,true}->
        merge(L1,L2,[]);
    {true,false}->
        merge(L1,mergesort(split(1,L2),split(2,L2),[]),[]);
    {false,true}->
        merge(mergesort(split(1,L1),split(2,L1),[]),L2,[]);
    {false,false}->
        merge(mergesort(split(1,L1),split(2,L1),[]),mergesort(split(1,L2),split(2,L2),[]),[])
    end.

merge([],[],R)->
    reverse(R);
merge(L,[],R)->
    merge(delete(min(L),L),[],[min(L)|R]);
merge([],L,R)->
    merge([],delete(min(L),L),[min(L)|R]);
merge([H1|T1],[H2|T2],R) when H1 < H2 ->
    merge(T1,[H2|T2],[H1|R]);
merge([H1|T1],[H2|T2],R) when H1 >= H2 ->
    merge([H1|T1],T2,[H2|R]).


split(1,L)->
    sublist(L,1,ceiling(length(L)/2));
split(2,L)->
    sublist(L,ceiling(length(L)/2+1),length(L)).

ceiling(X) when X < 0 ->    
    trunc(X);
ceiling(X) ->    
    T = trunc(X),
    case X - T == 0 of
        true -> T;
        false -> T + 1
    end.

However I'm irked by the fact that mergesort/3 is not tail recursive (TR), and is verbose.

I guess the problem here is that I'm not particularly aware of the TR 'template' that I would use here - I understand how I would implement a TR function that can be defined in terms of a series, for example - that would just move the arguments to the function up the series, however for the case in which we merge a sublist conditionally to the natural recursion of the rest of the list, I'm ignorant.

Therefore, I would like to ask:

1) How can I make mergesort/3 TR?

2) What resources can I use to understand erlang tail recursion in-depth?

Answer 1

Your merge-sort is not tail recursive because the last function called in mergesort/3 is merge/3. You call mergesort as arguments of merge so stack has to grow - upper called mergesort/3 is not yet finished and its stack frame can't be reused. To write it in TR approach you need think of it as much imperatively as you can. Every TR function is easily rewritable to iterational while loop. Consider:

loop(Arg) ->
    NewArg = something_happens_to(Arg),
    loop(NewArg) or return NewArg.

And:

data = something;
while(1){
    ...
    break loop or modify data block
    ...
} // data equals to NewArg at the end of iteration

Here is my TR merge-sort example. It's bottom-up way of thinking. I used merge/3 function from your module.

ms(L) ->
    ms_iteration([[N] || N <- L], []).

ms_iteration([], []) -> % nothing to do
    [];
ms_iteration([], [OneSortedList]) -> % nothing left to do
    OneSortedList;
ms_iteration([], MergedLists) ->
    ms_iteration(MergedLists, []); % next merging iteration
ms_iteration([L], MergedLists) -> % can't be merged yet but it's sorted
    ms_iteration([], [L | MergedLists]);
ms_iteration([L1, L2 | ToMergeTail], MergedLists) -> % merging two sorted lists
    ms_iteration(ToMergeTail, [merge(L1, L2, []) | MergedLists]).

It's nicely explained here: http://learnyousomeerlang.com/recursion .