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"). The comparator is curried: write fn a -> fn b -> a <= b; an uncurried fn (a, b) -> ... fails at runtime with an arity mismatch.

Stability caveat: the merge steps keep equal elements in input order only for a non-strict (<=) cmp, insertion sort only for a strict (<) cmp, and the comparison networks not reliably for either. Only mergesort_by (with <=) and insertion_sort_by (with <) are stable.

Design choices documented per function: timsort_by — 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))#

Leftist heap node: HLeaf | HNode(rank, value, left, right). Rank = length of rightmost path to a leaf. Invariant: rank(left) >= rank(right).

Design: Leftist heap provides O(log n) merge, insert, extract-min — all we need for heapsort. Simpler than Fibonacci or pairing heaps, with O(log n) worst-case (not amortized). Chosen for correctness clarity.

Functions

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

Appends two lists (xs then ys). O(|xs|); ys is shared, not copied.

Examples

march> Sort.append_list([1, 2], [3])
[1, 2, 3]

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

Heapsort over a leftist heap: inserts every element, then repeatedly extracts the minimum. Unstable, O(n log n) worst-case. Introsort's fallback once its quicksort recursion depth is exhausted.

Examples

march> Sort.heapsort_by([5, 2, 8, 1, 2], fn a -> fn b -> a <= b)
[1, 2, 2, 5, 8]
march> Sort.heapsort_by([], fn a -> fn b -> a <= b)
[]

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

Insertion sort, O(n²). Each element is inserted before the first element h of the sorted prefix with cmp(x)(h), so it is stable only for a strict < cmp; with <= equal elements come out reversed. Used by sort for 16..63 elements, where the quadratic cost is bounded.

Examples

march> Sort.insertion_sort_by([3, 1, 2], fn a -> fn b -> a <= b)
[1, 2, 3]
march> Sort.insertion_sort_by([(1, "x"), (1, "y"), (0, "z")], fn a -> fn b -> Tuple.first(a) < Tuple.first(b))
[(0, "z"), (1, "x"), (1, "y")]

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 sort_small_by (networks or mergesort) 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

Examples

march> Sort.introsort_by([20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1], fn a -> fn b -> a <= b)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
march> Sort.introsort_by([3, 1, 2], fn a -> fn b -> a > b)
[3, 2, 1]

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

Bottom-up mergesort: starts from singleton runs and merges adjacent pairs until one run remains. O(n log n). Stable when cmp is non-strict (<=): on a tie the earlier element is taken first. With a strict < equal elements come out reversed. Used as the fallback for sort_small_by when n > 8 (and so by introsort for 9..15-element slices).

Examples

march> Sort.mergesort_by([5, 2, 8, 1], fn a -> fn b -> a <= b)
[1, 2, 5, 8]
march> Sort.mergesort_by([(1, "x"), (1, "y"), (0, "z")], fn a -> fn b -> Tuple.first(a) <= Tuple.first(b))
[(0, "z"), (1, "x"), (1, "y")]

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

Reverses a list. O(n).

Examples

march> Sort.reverse_list([1, 2, 3])
[3, 2, 1]

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

for n <= 8, mergesort for 9..15)

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 chooses adaptivity over the worst-case bound. Stability is not guaranteed (see the module header).

Examples

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

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: NOT stable for n ≤ 8: the networks compare non-adjacent positions, so equal elements can be reordered whichever of < / <= is used (with <=, [(1, "x"), (1, "y"), (0, "z")] sorts to [(0, "z"), (1, "y"), (1, "x")]). For n > 8 see mergesort_by. 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.

Examples

march> Sort.sort_small_by([3, 1, 2], fn a -> fn b -> a <= b)
[1, 2, 3]
march> Sort.sort_small_by([9, 8, 7, 6, 5, 4, 3, 2, 1], fn a -> fn b -> a <= b)
[1, 2, 3, 4, 5, 6, 7, 8, 9]

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

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

Not guaranteed stable: runs are extended with insertion (stable only for a strict < cmp) and merged with merge steps (stable only for a non-strict <= cmp). With <=, [(1, "x"), (0, "a"), (1, "y")] keyed on the first component sorts to [(0, "a"), (1, "y"), (1, "x")].

Examples

march> Sort.timsort_by([5, 4, 3, 2, 1, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20], fn a -> fn b -> a <= b)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
march> Sort.timsort_by([], fn a -> fn b -> a <= b)
[]