Algorithms

Sort puts a Span<T> in order. BinarySearch, LowerBound and UpperBound find things in one that already is. Min, Max, Clamp and Swap are the four one-liners you would otherwise reach into <algorithm> for.

A comparator that is not a strict weak ordering — <= where you meant < — gives you a wrongly ordered span. It never gives you a write past the end of it, and that holds in release builds, where assertions are gone.

Sorting a span

Span<i32> values = arena.Push<i32>(count);
// ... fill ...

Sort(values);                                        // ascending, by operator<

Pass your own ordering with SortBy:

struct ByDepth
{
    bool operator()(const Renderable& a, const Renderable& b) const { return a.depth < b.depth; }
};

SortBy(renderables, ByDepth{});

A comparator is a template parameter, not a function pointer, and it is passed by value. That is the difference between the compiler inlining your comparison into the sort’s inner loop and the compiler seeing an opaque call it cannot optimise around. A published comparison of an inlined C++ sort against C’s qsort — one author, one workload, one machine — put the inlined form at 1.77×, of which only about 1.2× is the call itself; the rest is the optimisation an indirect call blocks in the code surrounding it. Nothing has measured Basalt’s own Sort against a function-pointer variant of it; the mechanism is what transfers, not the number.

A lambda works just as well:

SortBy(renderables, [](const Renderable& a, const Renderable& b) { return a.depth < b.depth; });

What Sort guarantees

Worst case	O(n log n). Not “usually” — there is no quadratic input
Allocation	None. Sort takes no arena, so it is callable from anywhere
Stack	At most 64 nested frames, measured at 4–5 KiB total
Stability	None. Equivalent elements may be reordered
Already sorted	One linear pass, then it returns

It is an introsort: quicksort with a median-of-three pivot, insertion sort for short runs, and a switch to heapsort once partitioning goes too deep. That last part is the whole point of the algorithm. Plain quicksort has inputs — not exotic ones, they can be constructed from a sorted array — that drive it to O(n²). Counting the partition depth and bailing out to heapsort turns those back into O(n log n). What the counter itself costs is one decrement and one compare per partition — no Basalt measurement of it exists, and the argument does not need one.

The stack bound comes from a second decision: the sort recurses into the smaller of the two partitions and loops on the larger. Each nested call therefore sees at most half of what its caller saw, so the nesting depth is at most floor(log2(count)) + 1 — 64 frames on a 64-bit machine, since count is a usize.

Unstable, and why there is no stable version yet

Equivalent elements may come out in a different relative order than they went in. There is no StableSort, and the reason is structural: every stable sorting algorithm buys stability with scratch memory. Being unstable is what lets Sort allocate nothing and take no arena.

For a POD element compared on the whole value, stability is unobservable anyway — two equal elements are indistinguishable after the swap. It matters only when you sort by part of the element, like records by name where equal names must keep their input order.

The comparator contract, and what happens when you break it

compare(a, b) must return true when a orders strictly before b. Strictly: compare(x, x) must be false.

The classic mistake is writing <=:

SortBy(values, [](const i32& a, const i32& b) { return a <= b; });   // WRONG

In most hand-written and many library quicksorts, that is not a wrong answer — it is memory corruption. The partition loops in a textbook quicksort are stopped by the comparator alone, so a comparator that never says “stop” lets the scan indices walk straight off the array. This is not hypothetical: Zig’s standard library shipped an out-of-bounds access of exactly this shape in its sort in September 2025.

Basalt’s loops carry their own index bounds and test them before asking the comparator anything. So:

	A textbook quicksort	Basalt’s Sort
What breaks	The scan indices run past the end of the array	Nothing. The loops stop on their own bounds
What you observe	Silent memory corruption, far from the call site and usually much later	The span comes back in some arbitrary order
In a release build	The same	The same. This guarantee does not depend on assertions

In a debug build you also get an assertion naming the problem, because the sort checks compare(pivot, pivot) once per partition — which catches the <= mistake specifically. That assertion is a diagnostic, not the defence. It compiles out in release, and the guarantee above does not.

The assert cannot catch everything

compare(x, x) == false is cheap to check and covers the common mistake. It does not prove your comparator is transitive. A comparator that is irreflexive but inconsistent — one derived from mutating state, or one that orders NaN arbitrarily — will still produce a wrong order. Safely, but wrongly.

Searching a sorted span

Four functions built on one primitive — literally one: the three named searches call it.

const usize first = LowerBound(scores, 50);   // first index not less than 50
const usize after = UpperBound(scores, 50);   // one past the last 50
const usize count = after - first;            // how many 50s there are

BinarySearch answers both halves of the real question — where, and whether:

const BinarySearchResult result = BinarySearch(scores, 50);
if (result.found)
{
    // scores[result.index] is the FIRST element equal to 50
}
else
{
    // 50 is not there; result.index is where it would be inserted
}

That shape is deliberate, and it is what Go, Zig and Rust all converged on. Zig converged on it by removing the alternative: its binarySearch used to return an optional index and was changed to return an index-and-found pair, because “there is still meaningful information to return to the caller, even if no acceptable item was found, namely: the index where an acceptable item could be inserted”.

A plain bool throws that away precisely when you need it. A nullable pointer throws it away too, and you can always recover a pointer from an index (items.data + result.index) while the reverse is impossible.

The index is the lower bound in both branches

When the value is present, index is the first of the equal elements, not an arbitrary one. Rust’s binary_search explicitly does not promise this. Here you can rely on it, so a hit on a run of duplicates needs no follow-up scan backwards.

Searching by a key that is not the element type

Two ways, and which one you want depends on whether you need to know whether it is there.

If you have an ordering against the key, hand it to any of the *By searches. The key gets its own deduced type, so no dummy element has to be fabricated to search with:

struct ByTimestamp
{
    bool operator()(const Record& r, const u64 t) const { return r.timestamp < t; }
    bool operator()(const u64 t, const Record& r) const { return t < r.timestamp; }
};

const BinarySearchResult hit = BinarySearchBy(records, deadline, ByTimestamp{});

Both operand orders are needed because UpperBoundBy applies the comparator the other way round and BinarySearchBy applies it both ways.

If the leading group is not an ordering against a key at all, use the primitive directly:

// The first record whose timestamp has reached the deadline.
const usize index = PartitionPoint(records, [deadline](const Record& r) { return r.timestamp < deadline; });

PartitionPoint returns the index of the first element for which the predicate is false. It returns 0 if none satisfies the predicate and items.size if all of them do. It cannot fail — and it is not a fourth implementation: LowerBoundBy and UpperBoundBy are each one call to it, so the loop above is the only copy of the index arithmetic in the header.

The precondition nobody checks

Every search function requires the span to be sorted by the same ordering. None of them verifies it, because checking is O(n) and would make an O(log n) function linear in debug builds.

What you get instead costs nothing:

On an unsorted span the answer is unspecified — but it is always a valid index in [0, size]. Never out of bounds, never undefined behaviour.

When you want to check deliberately, IsSorted and IsSortedBy are there for it:

BS_ASSERT(IsSortedBy(records, ByTimestamp{}), "records must be sorted before searching");

Min, Max, Clamp, Swap

const usize taken   = Min(available, requested);
const f32   opacity = Clamp(fade, 0.0f, 1.0f);
const usize clamped = Clamp(index, 0, count - 1);   // the bounds convert; `T` comes from `index`
Swap(current, previous);

Clamp takes its type from value alone and converts the two bounds, so clamping a usize index against integer literals compiles. Min and Max are symmetric and deduce from both arguments, so Min(1u, 2) does not — spell the type (Min<u32>(1u, 2)) or fix the arguments.

They return by value. std::min returns a reference, which is why the standard documentation carries a dangling-reference warning: bind its result to a const auto& when one argument was a temporary and you have a reference to a dead object. Returning by value cannot dangle.

Ties are documented, not accidental. Min(a, b) returns a and Max(a, b) returns b when the two compare equal. That makes the pair a stable two-element sort: { Min(a, b), Max(a, b) } keeps equivalent values in their input order.

Call	Result
Min(3, 5)	3
Max(3, 5)	5
Clamp(9, 0, 5)	5
Clamp(9, 5, 0) — inverted range	5, the low bound. Asserts in debug
Min(x, NaN)	x
Min(NaN, y)	NaN

Clamp with an inverted range is defined, not undefined

std::clamp says the behaviour is undefined if the bounds are backwards. Rust panics. Basalt does neither: it asserts in a debug build and computes Max(low, Min(value, high)), which yields low, in every build.

Both halves matter. The assertion tells you about the bug where it happened; the formula means a release build — where the assertion is gone — still has defined behaviour rather than whatever the optimiser felt like.

The assertion is skipped when Clamp is evaluated at compile time, so static_assert(Clamp(3, 10, 2) == 10) holds in every build. Without that, the same expression would be a hard compile error in a debug build and fine in a release one — which is precisely the debug/release split this function exists to avoid.

Min and Max on floats are comparisons, not IEEE minNum

fmin, Rust’s f64::min and Zig’s @min are all NaN-tolerant: given one NaN they return the other operand. Min and Max here are plain comparisons, so a NaN propagates or not depending on which side it is on, as the table above shows. That is deterministic and documented rather than undefined — but it is not the NaN-tolerant behaviour, and Basalt does not currently ship one. Giving the same name two different meanings by argument type would be worse than not having it.

Swap takes trivially copyable types only

Swap(a, b);       // three plain copies through a temporary

There is no Move, no Forward, and <utility> is not involved. Basalt’s containers already restrict their elements to trivially copyable types, and Sort works in the same regime. A move-only type — VirtualArray<T> is the one in the framework — is exactly the sort of object a generic algorithm should not be shuffling silently, so Swap refuses it at compile time.

Swap(x, x) is safe.

What is not here, on purpose

Not shipped	Because	What would change it
StableSort	Stability needs scratch memory; the unstable sort needs no arena at all	Sorting by a partial key where equal elements must keep input order
A pattern-adaptive sort (pdqsort)	Its main mechanism, branchless partitioning, is switched off by its own source for non-arithmetic elements or a custom comparator — which is Basalt’s normal case	A hot path sorting low-cardinality or reverse-ordered data
A branchless binary search	2.5–3× on cache-resident arrays, but parity or worse out of cache, and it depends on the compiler emitting a conditional move. Basalt ships MSVC and clang	A profile showing binary search hot, plus a two-compiler measurement
A three-way comparator	A sort consumes one bit per comparison; Rust’s own driver converts three-way comparators to two-way before the algorithm sees them	A search whose key type makes a two-way predicate awkward
SortByKey	A three-line comparator already expresses it, and a key-extractor form is a second instantiation of the whole algorithm	Enough call sites writing the same comparator by hand

Which header

Header	Holds	Include cost
basalt/core/Utility.h	Min, Max, Clamp, Swap, LessThan	Types.h, Assertions.h and Traits.h — the last of which includes nothing at all. That is all
basalt/core/Sort.h	Everything else on this page	The above, plus Span.h

They are split so that code which only wants to clamp an index does not pull in the sorting machinery. For the same reason Min and Max are not in Math.h — that header includes the compiler’s vendor intrinsics header unconditionally, and clamping an index should not cost you that.

API summary

Parameters, preconditions and the full contract are documented in basalt/core/Sort.h and basalt/core/Utility.h.

Sorting

Signature	Purpose
Sort(items)	Sorts in place, ascending, by operator<.
SortBy(items, compare)	Sorts in place under your ordering.
IsSorted(items)	Whether the span is in non-decreasing order. O(n).
IsSortedBy(items, compare)	The same under your ordering.

Searching

Signature	Purpose
BinarySearch(items, value)	{ index, found }. index is the lower bound either way.
BinarySearchBy(items, key, compare)	The same under your ordering, and key need not be the element type.
LowerBound(items, value)	First index not ordering before value.
UpperBound(items, value)	First index that value orders before.
LowerBoundBy / UpperBoundBy	The same under your ordering, with a key of any type the comparator accepts.
PartitionPoint(items, predicate)	First index where the predicate is false.

Scalars

Signature	Purpose
Min(a, b) / Max(a, b)	Smaller / larger, by value. Ties go to a / b.
Clamp(value, low, high)	Constrains to a closed range. low on an inverted range.
Swap(a, b)	Exchanges two trivially-copyable values.
LessThan<T>{}	The default ordering, as a functor you can pass on.