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[]required

the 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.