cakeml
cakeml copied to clipboard
Replace standard list sort with better sort
The default list sort has quadratic behavior on sorted (or nearly sorted) lists because it picks the pivot from the head of the list.
This issue is about potentially replacing:
https://github.com/CakeML/cakeml/blob/master/basis/ListProgScript.sml#L405
with the "OCaml-inspired" mergesort available in HOL.
#1206 partially resolved this by defining a central "sort" that is shared across the codebase.
The next step is to implement a fast sort replacing this standardized sort.