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

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

Reverses a list. O(n).

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

Appends two lists. O(|xs|).

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.

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.

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.

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.

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

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