std.sort

In-place ordering. Heapsort, because it is the one O(n log n) algorithm that needs no recursion (no diverge in the effect row), no scratch buffer (no alloc) and moves elements only with swap, so it sorts owners as happily as scalars. Cost: O(n log n) comparisons and swaps, no allocation; the order of equal elements is not kept.

// effects: diverge, ffi_precondition, indirect_call, read:less, read:xs, trap, write:xs
pub fn sort_by[T](n:usize, xs:rw<T>[n]@host, less:ro<fn(ro<T>, ro<T>) -> bool>)

// effects: diverge, ffi_precondition, indirect_call, local_read, local_write, read:xs, stack_storage, trap, write:xs,
// zero_init
pub fn sort[T:Ord](n:usize, xs:rw<T>[n]@host)

// Stable sort of unsigned keys, eight bits a pass, least significant first. Passes come in pairs, xs to scratch and
// back, and stop once the largest key has no digit left, so small keys pay for their width only. Cost: O(n) per pass,
// at most eight passes, no allocation: the caller lends scratch of the same extent.
// effects: ffi_precondition, local_read, local_write, read:scratch, read:xs, stack_storage, trap, write:scratch,
// write:xs, zero_init
pub fn radix_sort[T:unsigned](n:usize, xs:rw<T>[n]@host, scratch:rw<T>[n]@host)

// The index of a value equal to `key` in an already sorted view, if one is there.
// effects: diverge, ffi_precondition, local_read, local_write, read:key, read:xs, stack_storage, trap, zero_init
pub fn search[T:Ord](n:usize, xs:ro<T>[n]@host, key:ro<T>) -> Option[usize]

A generic function's effects are what it may do for any arguments within its bounds, besides what their own trait members do.