Landin library reference source

core/sort

Shared: available on every enabled target.

Allocation-free in-place heapsort and selection sort using ordering evidence.

The module supplies ordering for the ten integer scalars; core/text supplies UTF-8 byte ordering. Custom ordered evidence must obey a strict weak ordering. Neither algorithm promises stability.

Items

Executable example

This complete program is maintained in the repository runtime tests. View source.

import core/sort

exercise: () -> (ok: bool) =
    ok = false
    mut values: [3]i32 = [3, 1, 2]
    sort.sort(values[0..<3])
    ok = values[0] == 1 and values[1] == 2 and values[2] == 3
end exercise

public main: () -> (code: i32) =
    code = 1
    ok := exercise()
    if ok then
        code = 42
    end if
end main

ordered concept

public ordered: type = concept (item: type)
    --- Return true exactly when left precedes right under the strict weak
    --- ordering.
    less: (left: item, right: item) -> (yes: bool)
end ordered

core/sort/sort.ldn:3

Strict ordering evidence. less must be irreflexive and transitive, with consistent equivalence classes, for the duration of a sort.

sort function

public sort: (item: type is ordered, values: []mut item) -> none

core/sort/sort.ldn:82

Sort an initialized mutable slice in place using heapsort. Requires consistent ordered evidence; uses constant auxiliary storage, no allocation and O(n log n) comparisons. Equal items need not retain their order.

In-place heapsort for initialized views. Worst-case O(n log n) comparisons, constant auxiliary storage and bounded call depth. The caller supplies a strict ordering; stability is not promised.

sort_selection function

public sort_selection: (item: type is ordered, values: []mut item) -> none

core/sort/sort.ldn:106

Sort in place using selection sort. Performs n(n-1)/2 comparisons and at most n-1 swaps, with no allocation. Useful for tiny or expensive-to-swap items; it is not stable.

Selection sort for tiny or swap-expensive views. Exactly n(n-1)/2 comparisons, at most n-1 swaps, constant storage and bounded call depth.