sort

import sort from "sort";

sort sorts slices in place and searches sorted ones. tape has no generics, so the functions come from generators: you name the element type (and, for your own order, a comparison function) in a @tape block and get ordinary functions made for it. The common ones already exist, so sorting numbers or strings needs no @tape block at all:

var scores: [6]i64 = [420, 95, 1300, 420, 7, 860];
sort.sort_i64(scores[0..6]);                          // 7 95 420 420 860 1300
let at: ?i64 = sort.binary_search_i64(scores[0..6], 420);   // 2

The module is pure. It works in t1 and t2 (not t0: the stable sort allocates a scratch buffer).

Ready-made functions

Call them as sort.sort_i64(...). For any other type, use a generator.

Generators

gen_sort

pub @tape fn gen_sort(T: type)

Sorting by T’s natural order. Emits, into the module that calls it:

pub fn sort_$T(s: []T)                    // stable
pub fn sort_unstable_$T(s: []T)           // in place, no allocation
pub fn is_sorted_$T(s: []const T) -> bool

$T is the type’s name as a generator spells it: sort_u8, sort_Level for an enum Level, sort_cslice_u8 for []const u8.

The natural order is:

• numbers by value, unsigned types as unsigned;
• f32 and f64 by value with every NaN after every number, so a slice holding NaNs sorts and searches correctly (-0.0 and 0.0 count as equal);
• false before true;
• enums by their values;
• string, []const u8 and []u8 byte by byte, a prefix before the longer text ("app" before "apple", "Zebra" before "apple").

Any other type is a compile error: sort it with gen_sort_by.

import sort from "sort";

pub enum Level : u8 { High = 1; Mid = 4; Low = 7; }

@tape { sort.gen_sort(u8); sort.gen_sort(Level); }

var b: [4]u8 = [200, 3, 255, 0];
sort_u8(b[0..4]);                                      // 0 3 200 255
var l: [3]Level = [Level.Low, Level.High, Level.Mid];
sort_Level(l[0..3]);                                   // High Mid Low

gen_sort_by

pub @tape fn gen_sort_by(T: type, less: fn(*const T, *const T) -> bool)

Sorting by a function of yours: less(a, b) returns true when a must come before b. It takes const pointers, fn(a: *const T, b: *const T) -> bool, like every comparison function the stdlib takes; one declared with *T parameters is a compile error. The functions are named after it:

pub fn sort_by_$less(s: []T)
pub fn sort_unstable_by_$less(s: []T)
pub fn is_sorted_by_$less(s: []const T) -> bool

pub struct Player { name: []const u8; score: i64; }

fn higher_score(a: *const Player, b: *const Player) -> bool { return a.score > b.score; }

@tape { sort.gen_sort_by(Player, higher_score); }

sort_by_higher_score(players[0..5]);   // best first; equal scores keep their order

less must be a consistent order: never less(a, a), never both less(a, b) and less(b, a), and transitive. Use < or > on fields, not <=. If it isn’t, the elements end up in some order, but nothing breaks: no element is lost or duplicated, and nothing outside the slice is touched. less can’t change the elements it is given: its pointers are const.

The struct must be pub, because the generated functions are.

gen_search and gen_search_by

pub @tape fn gen_search(T: type)
pub @tape fn gen_search_by(T: type, less: fn(*const T, *const T) -> bool)

Binary search in a slice sorted by the same order:

pub fn binary_search_$T(s: []const T, x: T) -> ?i64
pub fn lower_bound_$T(s: []const T, x: T) -> i64
pub fn upper_bound_$T(s: []const T, x: T) -> i64
// gen_search_by: binary_search_by_$less, lower_bound_by_$less, upper_bound_by_$less

• binary_search returns the index of the first element equal to x, or null.
• lower_bound is where x would be inserted before any equal elements, upper_bound after them; the elements equal to x are s[lower_bound..upper_bound]. Both are s.len when x is greater than everything.

var scores: [6]i64 = [7, 95, 420, 420, 860, 1300];
let s: []const i64 = scores[0..6];
sort.binary_search_i64(s, 420);                         // 2
sort.upper_bound_i64(s, 420) - sort.lower_bound_i64(s, 420);   // 2 of them
sort.binary_search_i64(s, 500);                         // null
sort.lower_bound_i64(s, 500);                           // 4: where 500 would go

On a slice that isn’t sorted the result is meaningless, but always an index in range or null.

Stable or unstable?

sort_* is stable: elements that compare equal keep their order, so sorting players by score leaves players with the same score in the order they were in. It is a merge sort; for more than 20 elements it borrows a scratch buffer of half the slice’s length from the heap and gives it back before returning.

sort_unstable_* may reorder equal elements, allocates nothing, and is usually faster. Use it for numbers and anything where equal means identical.

Both take O(n log n) time in the worst case, and are fast on input that is already sorted.

Sorting moves elements; it never copies them. Sorting strings, or structs holding strings, allocates nothing for them.

Example

stdlib/examples/sort.tape:

@tape { sort.gen_sort_by(Player, higher_score); }

pub fn main() -> i32 {
    var scores: [6]i64 = [420, 95, 1300, 420, 7, 860];
    sort.sort_i64(scores[0..6]);
    io.println("scores: {scores[0]} {scores[1]} {scores[2]} {scores[3]} {scores[4]} {scores[5]}");
    let at: ?i64 = sort.binary_search_i64(scores[0..6], 420);
    io.println("first 420 at {at!}, {sort.upper_bound_i64(scores[0..6], 420) - at!} of them");
    if (sort.binary_search_i64(scores[0..6], 500) == null) {
        io.println("500 would go at {sort.lower_bound_i64(scores[0..6], 500)}");
    }

    var names: [4]string = ["mika", "Aino", "eero", "aada"];
    sort.sort_string(names[0..4]);
    io.println("names: {names[0]} {names[1]} {names[2]} {names[3]}");
    // ... players sorted with sort_by_higher_score ...
}

scores: 7 95 420 420 860 1300
first 420 at 2, 2 of them
500 would go at 4
names: Aino aada eero mika
1. aino 1300
2. ville 860
3. mika 420
4. aada 420
5. eero 95

Last modified: 2026-10-03 22:30:57 UTC