Sort

Sort

pub fn Sort<T>(Values: mut T[], Compare: fn(readonly T&, readonly T&) -> i32)
    where T: Movable, MoveAssignable

Rearranges a writable slice in ascending comparator order without allocation.

Iterative heapsort is unstable and performs O(n log n) comparisons/moves in the worst case with O(1) extra element storage. Every swap uses explicit move construction and assignment, supporting non-Copy T without raw bit copying. No recursion, hidden allocator, lock or unsafe block is introduced. Comparator and element lifecycle costs are additional work. Storage addresses remain fixed, but their logical element identities/values change during sorting. T: Element supporting safe move construction and move assignment. Values: Writable storage, exclusively protected from conflicting access during sorting. Compare: Safe borrowed comparison; negative/zero/positive orders Left against Right. Pre: Compare provides a consistent strict weak ordering and never invalidates Values. Warning: Sort is unstable; comparator traps use ordinary fatal semantics without rollback. Return: No value after ordering Values according to Compare; equal elements have no stability guarantee.

Example

module example.sort_slice;
from std.iteration import Sort, BinarySearch;
fn Compare(Left: i32&, Right: i32&) -> i32 {
    if Left < Right { return -1; }
    if Left > Right { return 1; }
    return 0;
}
fn Main() -> i32 {
    var Values: i32[5] = [42, -1, 20, 42, 0];
    Sort<i32>(Values, Compare);
    if Values[0] != -1 || Values[1] != 0 || Values[2] != 20 { return 1; }
    if Values[3] != 42 || Values[4] != 42 { return 2; }
    switch BinarySearch<i32>(Values, 42, Compare) {
        case .Ok { Value = Index } => { if Index != 3 { return 3; } }
        case .Err { Error = _ } => return 4;
    }
    return 0;
}