cakeml icon indicating copy to clipboard operation
cakeml copied to clipboard

Replace standard list sort with better sort

Open tanyongkiam opened this issue 1 year ago • 1 comments

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.

tanyongkiam avatar Feb 04 '24 03:02 tanyongkiam

#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.

tanyongkiam avatar Aug 25 '25 01:08 tanyongkiam