Improve performance of `Data.List.sort` by adding a (3,4,5)-way merge
Hiya, I believe I found a way to decently (up to ~20%) improve performance of the sort
in base
.
The simple optimization is to build on the current implementation, which is a simple merge sort which pre-scans the list for ascending and descending sequences, by adding a static 3-way merge which reduces internal function calls as well as calls to the comparison function passed by the user.
I also attempted 4-way and 5-way merges which improved performance further but not as significantly. The implemented sort as well as very rudimentary benchmarks are in my github repository.
I would like to open a pull request as well, but first gather some feedback. Specifically
- did I screw up in some way / is the sort not actually equivalent
- how could I more intricately benchmark the sort? -> Currently it only tests for one random list per size
- What n-way merge is "most worth it" -> You could take this ad absurdum and add a 100-way merge, which I'm sure we don't
Thanks in advance :)