nish/sort
xs.sort(cmp) on an array, in Nish: a stable merge sort, compiled once per comparator.
import {
sortWith,
} from "nish/sort";
export const main = (): i32 => {
const xs: i32[] = [3, 1, 2];
xs.sort((a, b) => a - b); // xs is now [1, 2, 3], and the call answers xs
return xs[0];
};
A program does not import this module
A .sort(cmp) call is what loads it
(the checker's importSort), and the checker routes the call to sortWith
here. cmp is a compile-time function parameter, so each comparator is an
instantiation of its own whose body calls the comparator directly — there is
no function pointer. Under Node and tsc the call is the platform's
Array.prototype.sort, so nothing here runs there.
Same order as Node
Array.prototype.sort is stable (ES2019), so for a
comparator that is a consistent total preorder there is exactly one answer,
and any stable sort gives it. A comparator's result is read only as "greater
than zero or not": a later element moves before an earlier one only when
the comparator answers a positive number for (earlier, later), so a negative
zero and NaN are zero, as Node treats them.
Shape
The array is copied once into a scratch array of the same
length, the only allocation, which the function's arena scope gives back
before it returns, so a sort leaves Arena.used() where it was. Runs of
RUN are sorted by insertion from the scratch into the array (a strictly
descending run is copied reversed instead), then merged
bottom-up, alternating between the two, and copied back once if the last
pass ended in the scratch. A pair of runs already in order is copied without
a merge. Every merge takes from the left run on a tie, which is what makes
it stable.
No element is held across a write
An interface element is stored
inline, and const v = xs[i] is a pointer into the array, so an insertion
sort in place would overwrite the element it is inserting. Every step here
reads from one array and writes the other, and moves a whole slot, which for
an inline record is one copy of its bytes.
Proofs
Every index is proven in range by the guard written beside it,
so no access keeps its bounds check. The run arithmetic wraps only where
the operands are proven to lie in 0..n, so it cannot wrap: a difference
of two of them, or a sum taken only when it stays below n.
Functions
sortWith
xs sorted in place by cmp, stably, and answered: what xs.sort(cmp)
compiles to.
const sortWith: <T>(
xs: T[],
cmp: (a: T, b: T) => number,
) => T[]
xsT[]requiredthe array to sort; its elements are rearranged in place.
cmp(a: T, b: T) => numberrequired
compares an earlier element with a later one: a positive answer
puts the later one first, and anything else, NaN and negative zero
included, keeps their order.
returnsT[]xs itself, the same array the call was given, now sorted.

