Skip to content

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 :)

Edited by Jade
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information