Skip to content

WIP: Improve Data.List.sort(By) (#24280)

Jade requested to merge wip/three-way-merge-sort into master

As discussed in #24280 as well as on the CLC github, this patch aims to implement an improved version of Data.List.sortBy and therefore Data.List.sort which increases performance by up to 20% on larger lists, but also ~10% on lists of size 100 and smaller. These nunbers are based off of a small benchmark I built for this implementation, that also tests for correctness and stability. Example results can be seen here, which also demonstrate that peak memory usage does not see any difference at all, and the amount of memory allocated and copied is lower with the improved version.

This approach implements a three-way merge which also aims to reuse comparisons as implemented by @int-e who also helped to fix a bug in my original version. The amount of merges required for any list should if I (and wolfram alpha) did the math correctly be cut in half by the three-way merge:

image image

Edited by Jade

Merge request reports