Sort

Sort module: Timsort, Introsort, and AlphaDev optimal comparison networks.

Internal module — users should import Enum, not Sort directly.

All functions operate on List(a) with a comparator (a -> a -> Bool). cmp x y = true means x should come before y (i.e., x is "less than or equal").

Design choices documented per function: timsort_by — stable, exploits natural runs, best on nearly-sorted input introsort_by — unstable, O(n log n) worst-case via heapsort fallback sort_small_by — optimal comparison networks (Dobbelaere / Floyd & Knuth 1966)

See specs/2026-03-19-sorting-and-enum-design.md for algorithm detail.

Types

ptypeHeapHeap(a) = HLeaf | HNode(Int, a, Heap(a), Heap(a))#

Functions

fnappend_listappend_list(xs : List(a), ys : List(a)) : List(a)#

Appends two lists. O(|xs|).

fnheapsort_byheapsort_by(xs : List(a), cmp : a -> a -> Bool) : List(a)#

fninsertion_sort_byinsertion_sort_by(xs : List(a), cmp : a -> a -> Bool) : List(a)#

Insertion sort. Stable, O(n²). Used for small sublists (n < 16) where quadratic cost is bounded.

fnintrosort_byintrosort_by(xs : List(a), cmp : a -> a -> Bool) : List(a)#

Introsort. Unstable, O(n log n) worst-case guaranteed.

Algorithm: starts with median-of-3 quicksort; switches to heapsort when
recursion depth exceeds 2*floor(log2(n)); uses AlphaDev/insertion sort for
n < 16. This prevents quicksort's O(n²) worst-case on adversarial inputs.

Note on list performance: partitioning a linked list requires O(n) single-pass
with three accumulators. Random-access middle element requires O(n/2) walk.
The algorithm is asymptotically O(n log n) but with a larger constant than
array-based introsort due to these costs.

Prefer over timsort_by or mergesort_by when:
  - worst-case O(n log n) is required (security-sensitive sorting)
  - input is adversarial or unknown shape

fnmergesort_bymergesort_by(xs : List(a), cmp : a -> a -> Bool) : List(a)#

Top-down mergesort. Stable, O(n log n). Used as the fallback for sort_small_by when n > 8, and as the heapsort-free path for introsort on very small inputs.

fnreverse_listreverse_list(xs : List(a)) : List(a)#

Reverses a list. O(n).

fnsortsort(xs : List(a), cmp : a -> a -> Bool) : List(a)#

Canonical sort entrypoint. Picks an algorithm appropriate for the input size:

n < 16 → sort_small_by (specialised straight-line sort networks

              with an insertion-sort fallback)
- n <  64  → `insertion_sort_by` (in-list, low overhead for small inputs)
- n >= 64  → `timsort_by` (stable, adapts to runs in real-world data)

Use `introsort_by` directly when you need worst-case O(n log n) on
adversarial inputs; the default `by` chooses stability + adaptivity
over the worst-case bound.

    Sort.sort([3, 1, 4, 1, 5, 9, 2, 6], fn a -> fn b -> a < b)
    -- [1, 1, 2, 3, 4, 5, 6, 9]

fnsort_small_bysort_small_by(xs : List(a), cmp : a -> a -> Bool) : List(a)#

Sorts a small list using optimal comparison networks for n ≤ 8. For n > 8, falls back to mergesort.

Algorithm: AlphaDev-inspired optimal sorting networks from Bert Dobbelaere's
catalog, proven optimal by Floyd & Knuth (1966). Comparator counts:
  n=2: 1, n:3: 3, n:4: 5, n:5: 9, n:6: 12, n:7: 16, n:8: 19

Stability: stable for n ≤ 8 (equal elements preserve original list order).
Complexity: O(1) for n ≤ 8 (fixed comparator count), O(n log n) for n > 8.

Use this:
  - as the base case in other sort algorithms (Introsort uses it for n < 16)
  - when sorting known-small collections
Prefer timsort_by or mergesort_by for general-purpose sorting.

fntimsort_bytimsort_by(xs : List(a), cmp : a -> a -> Bool) : List(a)#

Timsort. Stable, O(n log n) worst-case, O(n) on sorted input.

Algorithm: detect natural runs (ascending sequences), extend short runs to
MIN_RUN=16 via insertion sort, maintain a merge stack with the Timsort
invariants (|Z|>|Y|+|X|, |Y|>|X|), then drain the stack.

Prefer over mergesort_by when input is known to be partially sorted or
contains natural ascending runs (event logs, time-series, pre-sorted sublists).
On fully random input, performance is similar to mergesort_by.