std.sort

std.sort

std.sort.sort provides pure Janus, in-place sorting helpers for :core code. It performs no allocation and requires no capability.

Import

use std.sort.sort as sort

Generic Comparator Sorts

pub const INSERTION_SORT_CUTOFF: usize = 32
pub const ADAPTIVE_SORT_CUTOFF: usize = 64

pub func insertion_sort_by[T](
    edit arr: []T,
    len: usize,
    less: func(T, T) -> bool,
) -> void

pub func quicksort_by[T](
    edit arr: []T,
    len: usize,
    less: func(T, T) -> bool,
) -> void

pub func sort_by[T](
    edit arr: []T,
    len: usize,
    less: func(T, T) -> bool,
) -> void

less(a, b) returns true when a should appear before b.

sort_by uses insertion sort for slices smaller than ADAPTIVE_SORT_CUTOFF and median-of-three quicksort for larger slices. quicksort_by falls back to insertion sort for subranges smaller than INSERTION_SORT_CUTOFF.

Comparator quicksort is not stable. Equal elements may be reordered.

Concrete Ascending Sorts

pub func insertion_sort_i64(edit arr: []i64, len: usize) -> void
pub func quicksort_i64(edit arr: []i64, len: usize) -> void
pub func sort_i64(edit arr: []i64, len: usize) -> void

pub func insertion_sort_u64(edit arr: []u64, len: usize) -> void
pub func quicksort_u64(edit arr: []u64, len: usize) -> void
pub func sort_u64(edit arr: []u64, len: usize) -> void

The concrete sort_i64 and sort_u64 helpers use the same adaptive shape: insertion sort for small slices, quicksort for larger slices.

Example

use std.sort.sort as sort

func less_i64(a: i64, b: i64) -> bool do
    return a < b
end

func main() -> i32 do
    var arr = [_]i64{4, 1, 3, 2}
    sort.sort_by[i64](arr, 4, less_i64)

    if arr[0] != 1 do return 1 end
    if arr[3] != 4 do return 2 end
    return 0
end

Verification

cd janus
./scripts/zb test-sort

The smoke covers insertion sort, quicksort, adaptive concrete sorting, and large generic comparator sorting that forces the quicksort path.