[erlang-questions] algorithm of lists:sort?

[Motiejus Jakštys]

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