Hi Niols,

The repository in question is very experimental. Our implementation of
TimSort on list is indeed broken. I can't remember if it contains the
famous TimSort bug, but we are aware that it exists and know of two ways
to fix it. We quickly switched to working on arrays, though, and were
planning on coming back to list eventually.

Our implementation of TimSort on arrays can be found here:

https://github.com/LesBoloss-es/sorting/blob/master/src/array/timsort.ml

It does include a fix of the bug. We have tested it successfully on a
rather wide range of arrays.

So interesting that you mentioned this :) I actually came across your implementation as I was looking for an OCaml implementation of TimSort that I could use as a test stress for Cameleer (a deductive verification tool for OCaml-written code).

I didn't get that much far (cf, the in-progress proof is here: https://github.com/ocaml-gospel/cameleer/blob/master/examples/in_progress/timsort.ml), but I was planning to get back to it very soon. Maybe I will take a look first at the implementation on arrays :)

Cheers

Mário