[erlang-questions] algorithm of lists:sort?

[Loïc Hoguin]

I was wondering whether some of them could be removed now that the 
compiler optimizes a lot more things than when I suppose it was written?

On 11/21/2012 10:42 PM, Paul Fisher wrote:
> It is a merge sort.  My recollection last I looked is that all the extra functions and patterns are manually unrolled optimizations.
>
>
> --
> paul
>
> On Nov 21, 2012, at 1:48 PM, "Motiejus Jakštys" <desired.mta@REDACTED> wrote:
>
>> Hi,
>>
>> I am looking at implementation of lists:sort. I need to describe it to
>> my colleague, so he can implement an analogous version in C++ (he does
>> not know Erlang). Looking at the code it is very non-obvious how it
>> works. There is a lot of pattern matching, but it is very hard to get
>> the picture. Trapexit[1] says it's a merge sort. But why is the
>> implementation so big?
>>
>> Functions involved in lists:sort:
>> sort_1
>> split_1
>> split_1_1
>> split_2
>> split_2_1
>> rmergel
>> mergel
>> merge3_1
>> merge3_12
>> merge3_21
>> merge2_1
>> merge2_2
>> ... and so on ...
>>
>> If anyone knows its internals, I would very much appreciate a high
>> level description of the algorithm. Maybe with brief description what
>> the merge_x_x and split_x_x functions are doing?
>>
>> [1]: http://www.trapexit.org/String_Sort_List
>>
>> Thanks,
>> Motiejus
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questions@REDACTED
>> http://erlang.org/mailman/listinfo/erlang-questions
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>


-- 
Loïc Hoguin
Erlang Cowboy
Nine Nines
http://ninenines.eu