[erlang-questions] algorithm of lists:sort?

[Paul Fisher]

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