Timsort (powersort) for ATS2/Postiats and C
-------------------------------------------

Implementations of natural mergesort employing the ‘powerset’
strategy. ‘Powersort’ is the strategy employed in later versions of
Timsort—that is, in the sort implementation of the C-Python
interpreter.

Included:

  * An array sort, for ATS2, that supports linear types. The insertion
    sort uses binary search, and the merge uses galloping if this
    seems to help.

  * Sort functions for C, which are the foregoing array sort
    specialized for particular C types. Probably the most important of
    these types is void pointers, which can be used to sort heap
    objects, arrays of general elements, arrays of bytes, etc. Also
    supported are numerous integer and floating point types.

    The interfaces are ‘true’ C functions: there is no special runtime
    code needed. Both ‘envless’ and ‘reentrant’ (‘env-full’)
    interfaces are available.

  * Sort functions for C, to sort arrays of arrays of bytes, returning
    pointers and not altering the original data.

  * Sort functions for C, to sort arrays of bytes, perhaps altering
    the original data. These functions in fact sort arrays of
    pointers, but then copy the data, in sorted order, to some
    location. If that location is identical to or overlaps with the
    original data, the data is copied first, in sorted order, to a
    temporary buffer. (We tried permuting data in place, which would
    use less memory, but that method was slower. We also considered
    writing a sort that merged the original data instead of pointers,
    but doing so did not seem worth the effort. Memory usually is not
    a stumbling block, these days.)

  * A linked-list sort, for ATS2, that supports linear types. The
    insertion sort is straightforward. (Neither binary search nor
    galloping seems applicable.) The sort uses only constant-size
    extra space.

  * A linked-list sort, for ATS2, for non-linear lists. This is a
    wrapper around the sort for linear lists, and is guaranteed to
    make a fresh copy of each node.

It is possible to make it so you do not need ATS2 to compile the
program, as long as someone has already generated the C code from the
ATS2. However, I have not yet decided whether to implement this
ability. The C generated by patsopt is impenetrable; therefore, if you
had to modify the programs, you would almost certainly need
ATS2. Fortunately ATS2 is not very difficult to install; it requires
only standard C and optionally the GNU Multiple Precision Library.


References on the algorithms:

  * listsort.txt (https://archive.ph/XWTy3)

  * J. Ian Munro and Sebastian Wild, ‘Nearly-optimal mergesorts: fast,
    practical sorting methods that optimally adapt to existing
    runs’, 10 May 2018. arXiv:1805.04154v1.

  * H. Bottenbruch, "Structure and use of ALGOL 60", Journal of the
    ACM, Volume 9, Issue 2, April 1962, pp.161-221.
    https://doi.org/10.1145/321119.321120 (Pages 214 and 215 describe
    how to do a binary search.)

  * https://en.wikipedia.org/w/index.php?title=Binary_search_algorithm&oldid=1062988272#Alternative_procedure