O(n log n) lower bound, and why "just call the stdlib" is the right answer 95% of the time and the wrong answer the other 5%;O(n^2) trap hiding in the naive version, and how median-of-three plus a small-array cutoff turns it into something you would ship;O(n log n) guarantee that never degrades, at the cost of a scratch buffer, and why "stable" is a correctness property, not a performance one;O(n log n) worst case and zero extra memory, built straight on the sift-down we will write, and why it still loses to quicksort in practice;std.mem.sort, std.sort.pdq, std.sort.heap, std.sort.insertion), how the context + lessThan comparator works, and the std.sort.asc/std.sort.desc helpers;qsort), Rust (sort vs sort_unstable), and Go (sort.Slice / slices.Sort), and why the safety and stability stories differ across the four.fn sort(comptime T: type, items: []T, ...) and works for any element type;lessThan comparator around, which is Zig's way of saying "sort by whatever order you decide";Learn Zig Series):Two weeks ago we built a memory pool, last week we grew it into a slab allocator, and I closed episode 115 by pointing at the one thing that was still missing: concurrency. That is coming, but not today -- because before we hand memory to a hundred threads, we are going to take a breath and look at the single most-studied problem in all of computer science, the one every student implements and every senior engineer stops implementing: sorting. And I mean that literally -- by the end of this post my strongest advice will be "call std.mem.sort and move on with your life". But you cannot know when to trust the stdlib, or why it is shaped the way it is, until you have written the four classic sorts by hand and felt where each one hurts. So we write them, we test them properly, and we compare. First though -- the allocator debt from last week, all three exercises, with real code ;-)
Exercise 1 -- route oversized requests to the backing allocator. The slab allocator returned error.TooBig for anything over 1024 bytes. The hard part the exercise flagged is recognition: on free, a request that came from the backing allocator must NOT be masked down to a fake slab header (a wild mask can scribble on an unrelated slab). The reliable fix is a side table -- a hash map of the large pointers we handed out. On free we check the map first; a hit means "large alloc, free via backing", a miss means "must be a slab object, mask it". This can never false-positive, because the only pointers ever inserted are ones the large path returned, and slab objects are never inserted:
const CLASSES = [_]usize{ 16, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768, 1024 };
const SlabAllocator = struct {
backing: std.mem.Allocator,
caches: [CLASSES.len]SlabCache,
large: std.AutoHashMapUnmanaged(usize, usize) = .empty, // ptr -> len for oversized allocs
fn alloc(self: *SlabAllocator, size: usize) !*anyopaque {
const idx = classFor(size) orelse {
const mem = try self.backing.alignedAlloc(u8, .fromByteUnits(OBJ_ALIGN), size);
try self.large.put(self.backing, @intFromPtr(mem.ptr), mem.len);
return @ptrCast(mem.ptr);
};
return self.caches[idx].alloc();
}
fn free(self: *SlabAllocator, ptr: *anyopaque) void {
if (self.large.fetchRemove(@intFromPtr(ptr))) |kv| { // recognised large alloc, never masked
const many: [*]align(OBJ_ALIGN) u8 = @ptrCast(@alignCast(ptr));
self.backing.free(many[0..kv.value]);
return;
}
const slab: *Slab = @ptrFromInt(@intFromPtr(ptr) & ~(SLAB_SIZE - 1));
slab.cache.freeObject(slab, ptr);
}
fn deinit(self: *SlabAllocator) void {
for (&self.caches) |*c| c.deinit();
self.large.deinit(self.backing);
}
};
The map costs a little memory and a hash lookup per free, but only for the large path -- slab objects pay nothing extra, since the fetchRemove miss on a slab pointer is a single hash probe. The alternative some allocators use is a magic sentinel written at the header location, but a sentinel can collide with real object bytes; the side table is boring and correct, and boring-and-correct wins in allocator code every time.
Exercise 2 -- add the debug liveness flag to slabs. Last week's flat pool got a one-byte-per-object is_free array; here we generalise it to a debug-only bitset, one bit per object in the slab, allocated in grow. We set the bit in alloc, clear it in freeObject, and @panic on a double-free or an out-of-range index. In Release the whole live field is void and every branch compiles away:
const Slab = struct {
backing: []align(SLAB_SIZE) u8,
free_list: ?*FreeNode,
used: usize,
capacity: usize,
cache: *SlabCache,
live: if (builtin.mode == .Debug) []u8 else void, // one bit per object, Debug only
prev: ?*Slab = null,
next: ?*Slab = null,
};
// inside SlabCache, computing an object's index within its slab:
fn indexOf(self: *SlabCache, slab: *Slab, ptr: *anyopaque) usize {
const base = @intFromPtr(slab.backing.ptr) + self.data_start;
return (@intFromPtr(ptr) - base) / self.obj_size;
}
fn freeObject(self: *SlabCache, slab: *Slab, ptr: *anyopaque) void {
if (builtin.mode == .Debug) {
const idx = self.indexOf(slab, ptr);
if (idx >= slab.capacity) @panic("slab free: pointer not from this cache");
const bit = (@as(u8, 1) << @intCast(idx % 8));
if (slab.live[idx / 8] & bit == 0) @panic("slab double free"); // O(1) detection
slab.live[idx / 8] &= ~bit;
}
const node: *FreeNode = @ptrCast(@alignCast(ptr));
// ... rest of the free logic from episode 115, unchanged ...
_ = node;
}
The bitset is (capacity + 7) / 8 bytes -- for a 64 KiB slab of 16-byte objects that is roughly 4000 objects, so 500 bytes of debug overhead per slab and zero in release. That is the honest cost of catching a whole category of use-after-free bugs during testing while paying nothing in production. Nota bene the index-range check doubles as a guard against freeing a pointer this cache never owned -- a masked wild pointer whose slab-relative index lands past capacity trips the first @panic in stead of corrupting bookkeeping.
Exercise 3 -- wrap it in the std.mem.Allocator interface. This is the type-erasure pattern from episodes 13 and 26: give the allocator an allocator(self) method that returns a std.mem.Allocator carrying a *anyopaque context and a vtable. In Zig 0.16 the vtable has four functions -- alloc, resize, remap, free. Here is the wiring (the teaching version forwards to the backing allocator so you can see the plumbing clearly; the real one routes through caches[classFor(len)]):
fn allocator(self: *SlabAllocator) std.mem.Allocator {
return .{ .ptr = self, .vtable = &vtable };
}
const vtable = std.mem.Allocator.VTable{
.alloc = vtAlloc,
.resize = vtResize,
.remap = vtRemap,
.free = vtFree,
};
fn vtAlloc(ctx: *anyopaque, len: usize, alignment: std.mem.Alignment, ret_addr: usize) ?[*]u8 {
const self: *SlabAllocator = @ptrCast(@alignCast(ctx));
return self.backing.vtable.alloc(self.backing.ptr, len, alignment, ret_addr);
}
fn vtResize(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, ret: usize) bool {
const self: *SlabAllocator = @ptrCast(@alignCast(ctx));
return self.backing.vtable.resize(self.backing.ptr, mem, a, new_len, ret);
}
fn vtRemap(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, ret: usize) ?[*]u8 {
const self: *SlabAllocator = @ptrCast(@alignCast(ctx));
return self.backing.vtable.remap(self.backing.ptr, mem, a, new_len, ret);
}
fn vtFree(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, ret: usize) void {
const self: *SlabAllocator = @ptrCast(@alignCast(ctx));
self.backing.vtable.free(self.backing.ptr, mem, a, ret);
}
And the payoff -- once wrapped, the slab allocator drives any stdlib container that takes an allocator:
test "slab allocator behind the std.mem.Allocator interface drives an ArrayList" {
var sa = SlabAllocator{ .backing = std.testing.allocator };
const a = sa.allocator();
var list: std.ArrayList(u32) = .empty;
defer list.deinit(a);
for (0..1000) |i| try list.append(a, @intCast(i));
try std.testing.expectEqual(@as(u32, 999), list.items[999]);
}
The right design decision for resize, which the exercise hinted at: a resize that stays inside the same size class is free (the object already has room and you return true), while one that crosses a class boundary must fail the in-place resize (return false) and let the caller allocate-and-copy. That is exactly what makes a slab allocator a poor fit behind a growable ArrayList -- lots of cross-class resizes -- and a great fit behind fixed-size object pools. Right, debt paid in full. On to sorting ;-)
Sorting is deceptively deep. The problem is trivial to state -- put these elements in order -- and yet there is a hard mathematical floor underneath it: any sort that works by comparing pairs of elements needs at least O(n log n) comparisons in the worst case. The proof is a counting argument (there are n! possible orderings, each comparison gives one bit of information, and you need log2(n!) bits to pin down the right one, which is O(n log n)), and it tells you something practical: quicksort, merge sort, and heapsort are all optimal, they just trade how they hit that floor. You only beat O(n log n) by refusing to compare at all -- radix and counting sorts exploit the structure of the keys (digits, bounded integers) in stead of comparing, and buy O(n) at the cost of generality. We stay in the comparison world today, because that is what the stdlib gives you and what you reach for 95% of the time.
Every sort we write shares one signature, and it is worth staring at before we fill it in:
fn insertionSort(comptime T: type, items: []T, lessThan: fn (T, T) bool) void {
Three ideas from earlier episodes, stacked. comptime T: type makes it generic (episode 14) -- one function sorts []u8, []f64, or []MyStruct. items: []T is a slice (episode 5), so it sorts an array, an ArrayList's items, or any window into a buffer. And lessThan: fn (T, T) bool is the part that makes it yours: you pass the ordering. Ascending, descending, by-the-third-field, case-insensitive -- the algorithm does not care, it only ever asks "does a come before b?". Separating the mechanism (the sort) from the policy (the order) is the single most important design idea in this whole episode.
Insertion sort is what your hands do with a deck of cards: pick up the next card, slide it left past every card bigger than it, drop it in place. It is O(n^2) in the worst case and everyone learns to dismiss it -- which is a mistake, because on small and nearly-sorted inputs it is the fastest thing there is, no contest. Here it is:
fn insertionSort(comptime T: type, items: []T, lessThan: fn (T, T) bool) void {
var i: usize = 1;
while (i < items.len) : (i += 1) {
const key = items[i];
var j: usize = i;
while (j > 0 and lessThan(key, items[j - 1])) : (j -= 1) {
items[j] = items[j - 1];
}
items[j] = key;
}
}
Why is it fast where it counts? Two reasons. First, the inner loop does nothing when the element is already in place -- on an already-sorted array it is a single failed comparison per element, so O(n), and on a nearly-sorted one it is close to that. Second, it moves through memory in perfectly predictable, cache-friendly forward order with tiny constant factors -- no recursion, no extra buffer, no pivot bookkeeping. That is exactly why every serious quicksort (including Zig's) switches to insertion sort once a partition gets small, and why merge sort implementations use it for the leaves. It is also stable and in-place, two properties we will define precisely in a moment. Do not sneer at it -- respect it as the specialist it is.
Quicksort is the one everybody means when they say "sorting". Pick a pivot, partition the array so everything smaller sits left of it and everything larger sits right, then recurse on each side. It sorts in place, its average case is a beautiful O(n log n) with small constants, and it is usually the fastest general sort on real hardware. It also has a landmine: pick pivots badly and it degrades to O(n^2). Let me show the clean Lomuto partition first -- pivot is the last element, walk a "boundary" index i that marks where the next smaller-than-pivot element goes:
fn partition(comptime T: type, items: []T, lessThan: fn (T, T) bool) usize {
const pivot = items[items.len - 1];
var i: usize = 0;
var j: usize = 0;
while (j < items.len - 1) : (j += 1) {
if (lessThan(items[j], pivot)) {
std.mem.swap(T, &items[i], &items[j]);
i += 1;
}
}
std.mem.swap(T, &items[i], &items[items.len - 1]); // drop pivot into its final slot
return i;
}
fn quicksort(comptime T: type, items: []T, lessThan: fn (T, T) bool) void {
if (items.len <= 1) return;
const p = partition(T, items, lessThan);
quicksort(T, items[0..p], lessThan);
quicksort(T, items[p + 1 ..], lessThan);
}
Read the recursion carefully: after partition returns index p, items[p] is in its final sorted position (it is the pivot, and everything smaller is left, everything larger is right), so we recurse on items[0..p] and items[p+1..] and skip p itself. Slicing does the bookkeeping -- no lo/hi index arithmetic, no chance of an off-by-one on the bounds, because the slice is the bound. This is where Zig's slices quietly earn their keep.
Now the trap. This naive version takes the last element as pivot. Feed it an already-sorted array and every partition splits into a size-0 and a size-(n-1) piece -- n levels of recursion, O(n^2) comparisons, and (worse) O(n) stack depth that can blow the stack. The fix has two parts: choose a smarter pivot (median-of-three samples the first, middle, and last element and uses their median, which makes the sorted-input worst case vanish), and stop recursing on tiny slices (hand anything under ~16 elements to insertion sort). Both together give the version you would actually ship:
fn hybridSort(comptime T: type, items: []T, lessThan: fn (T, T) bool) void {
const CUTOFF = 16;
if (items.len <= CUTOFF) {
insertionSort(T, items, lessThan); // small slices: insertion wins outright
return;
}
medianOfThree(T, items, lessThan); // stash a good pivot at the end
const pivot = items[items.len - 1];
var i: usize = 0;
var j: usize = 0;
while (j < items.len - 1) : (j += 1) {
if (lessThan(items[j], pivot)) {
std.mem.swap(T, &items[i], &items[j]);
i += 1;
}
}
std.mem.swap(T, &items[i], &items[items.len - 1]);
hybridSort(T, items[0..i], lessThan);
hybridSort(T, items[i + 1 ..], lessThan);
}
where medianOfThree sorts the three sample positions and parks the median at the end to serve as pivot:
fn medianOfThree(comptime T: type, items: []T, lessThan: fn (T, T) bool) void {
const mid = items.len / 2;
const last = items.len - 1;
if (lessThan(items[mid], items[0])) std.mem.swap(T, &items[mid], &items[0]);
if (lessThan(items[last], items[0])) std.mem.swap(T, &items[last], &items[0]);
if (lessThan(items[last], items[mid])) std.mem.swap(T, &items[last], &items[mid]);
std.mem.swap(T, &items[mid], &items[last]); // median now sits at the pivot slot
}
This is 90% of what a production quicksort is. The remaining 10% -- the part that turns quicksort into introsort -- is a recursion-depth counter that bails out to heapsort if the depth exceeds ~2*log(n), guaranteeing O(n log n) even against an adversary who hand-crafts a worst-case input. That guarantee is exactly what the stdlib gives you, which is a nice segue: hold the thought, we will meet it below.
Quicksort is fast but its worst case is bad and it is unstable (more on that word in a second). Merge sort trades in-place-ness for two rock-solid guarantees: O(n log n) always, never degrading, and stability. It splits the slice in half, sorts each half, then merges the two sorted halves by repeatedly taking the smaller front element. The merge needs somewhere to put the output, so it uses a scratch buffer the same length as the slice:
fn mergeSort(comptime T: type, items: []T, buf: []T, lessThan: fn (T, T) bool) void {
if (items.len <= 1) return;
const mid = items.len / 2;
mergeSort(T, items[0..mid], buf[0..mid], lessThan);
mergeSort(T, items[mid..], buf[mid..], lessThan);
var i: usize = 0; // read cursor into the left half
var j: usize = mid; // read cursor into the right half
var k: usize = 0; // write cursor into the scratch buffer
while (i < mid and j < items.len) : (k += 1) {
// NOT-less-than keeps EQUAL elements in left-then-right order: this is what makes it stable
if (!lessThan(items[j], items[i])) {
buf[k] = items[i];
i += 1;
} else {
buf[k] = items[j];
j += 1;
}
}
while (i < mid) : (i += 1) { buf[k] = items[i]; k += 1; }
while (j < items.len) : (j += 1) { buf[k] = items[j]; k += 1; }
@memcpy(items, buf[0..items.len]);
}
The one subtle line is the merge comparison. I wrote if (!lessThan(items[j], items[i])) -- "if the right element is NOT strictly less than the left, take the left". When two elements are equal, neither is less than the other, so this takes the left one first -- and the left half held the elements that were earlier in the original array. That is stability: equal elements come out in the same relative order they went in. It sounds academic until you sort a table of people by age when they are already sorted by name, and you want ties-on-age to stay alphabetical. A stable sort gives you that for free; an unstable one scrambles it. Merge sort and insertion sort are stable; plain quicksort and heapsort are not.
The cost is the buf scratch of n elements -- merge sort is not in-place. There are in-place merge variants, but they are fiddly and slower, which is why the practical answer is "use the scratch buffer and enjoy the guarantee". Notice we pass buf sliced in exact parallel with items, so each recursive call gets its own private scratch window and there is never any aliasing between siblings.
Heapsort is the one that gives you both things quicksort and merge sort each only give you one of: O(n log n) worst case (like merge sort) and in-place, no scratch buffer (like quicksort). The trick is to treat the array as a binary max-heap -- a tree where every parent is >= its children, laid out implicitly so node i's children are at 2i+1 and 2i+2. You build the heap, then repeatedly swap the max (always at index 0) to the end and shrink the heap by one. The workhorse is siftDown, which pushes an out-of-place element down to where it belongs:
fn siftDown(comptime T: type, items: []T, start: usize, lessThan: fn (T, T) bool) void {
var root = start;
while (true) {
var child = 2 * root + 1;
if (child >= items.len) break; // root has no children -> done
// pick the larger of the two children
if (child + 1 < items.len and lessThan(items[child], items[child + 1])) child += 1;
if (!lessThan(items[root], items[child])) break; // heap property already holds
std.mem.swap(T, &items[root], &items[child]);
root = child;
}
}
fn heapSort(comptime T: type, items: []T, lessThan: fn (T, T) bool) void {
if (items.len <= 1) return;
var start = items.len / 2; // last parent node
while (start > 0) {
start -= 1;
siftDown(T, items, start, lessThan); // build the heap bottom-up: O(n)
}
var end = items.len;
while (end > 1) {
end -= 1;
std.mem.swap(T, &items[0], &items[end]); // biggest element to the back
siftDown(T, items[0..end], 0, lessThan); // restore heap over the shrunk range
}
}
So why, if it is O(n log n) worst-case and needs no extra memory, is heapsort usually slower than quicksort in practice? Cache behaviour. siftDown jumps around the array in a parent-to-child pattern that hops by ever-larger strides -- exactly the access pattern hardware prefetchers hate, so heapsort suffers cache miss after cache miss, while quicksort's partition scans memory in tidy sequential sweeps the prefetcher loves. Same asymptotic class, wildly different constant, because -- as I keep saying in this data-structures arc -- the hardware charges you for memory shape, not for O-notation. Heapsort's real job today is to be the safety net inside introsort: when quicksort's recursion goes too deep, you fall back to heapsort's guaranteed bound and never hit O(n^2).
Here is the punchline I promised: you should almost never write any of the above. Zig's standard library gives you battle-tested, benchmarked sorts, and std.mem.sort is the one you want by default -- it is a block sort (a stable, O(n log n), low-memory merge variant). There is also std.sort.pdq (pattern-defeating quicksort -- unstable, but blisteringly fast and hardened against the O(n^2) adversary), plus std.sort.insertion and std.sort.heap when you specifically want those. They all share the same call shape: element type, slice, a context value, and a lessThan(context, a, b) function:
const Person = struct { name: []const u8, age: u8 };
fn byAge(_: void, a: Person, b: Person) bool {
return a.age < b.age;
}
test "std.mem.sort with a field comparator" {
var people = [_]Person{
.{ .name = "Ada", .age = 36 },
.{ .name = "Linus", .age = 25 },
.{ .name = "Grace", .age = 36 },
.{ .name = "Dennis", .age = 41 },
};
std.mem.sort(Person, &people, {}, byAge);
try std.testing.expectEqual(@as(u8, 25), people[0].age);
try std.testing.expectEqual(@as(u8, 41), people[3].age);
}
Notice the third argument {} -- that is Zig's empty value, passed as the context because byAge ignores it (the _: void first parameter). The context exists for sorts that need extra state the comparator cannot capture -- say, sorting an array of indices by looking up a separate array of keys; you pass that key array as context and the comparator reads through it. It is the same "mechanism vs policy" split from our hand-written versions, just with the policy allowed to carry luggage.
For the common numeric cases the stdlib hands you the comparator too -- std.sort.asc(T) and std.sort.desc(T):
test "ascending and descending built-in comparators" {
var xs = [_]i64{ 3, 1, 4, 1, 5, 9, 2, 6 };
std.mem.sort(i64, &xs, {}, std.sort.asc(i64));
try std.testing.expectEqual(@as(i64, 1), xs[0]);
std.mem.sort(i64, &xs, {}, std.sort.desc(i64));
try std.testing.expectEqual(@as(i64, 9), xs[0]);
}
And when stability matters -- ties must preserve input order -- reach for std.mem.sort or std.sort.insertion (both stable) rather than std.sort.pdq (fast but unstable). Having said that, if you do not care about ties, std.sort.pdq is the throughput champion. Choose stable when correctness depends on tie order, choose pdq when you just want it sorted fast.
The comparator-as-parameter design is the whole reason one sort function serves every type and every order, and Zig expresses it without a scrap of runtime overhead. When you write std.sort.asc(i64), that is a comptime function returning a comparator function specialised to i64; the compiler inlines it into the sort, so there is no indirect call, no vtable, nothing -- the generated machine code is as tight as if you had hand-written a < b in the loop. Compare that to C's qsort, where the comparator is a genuine runtime function pointer the compiler usually cannot inline, so every single comparison pays an indirect call. Zig gives you the generality of a callback with the speed of an inlined literal, and that is comptime doing exactly what episode 9 promised.
The second place the type system shows up is in what cannot go wrong. Our sorts take items: []T, and every index into that slice is bounds-checked in safe builds -- the classic partition off-by-one that reads one past the pivot does not silently corrupt memory, it traps at the exact line. The comparator's type is checked too: pass a fn (Foo, Foo) bool to a sort over []Bar and it is a compile error, not a segfault. In C, qsort hands your comparator two const void* and you cast them back to the right type by hand -- get that cast wrong and the compiler cannot help you. Zig's generics mean the element type flows through the whole sort, so the mistake is caught before the program ever runs.
Most people test a sort with three hand-picked arrays and call it a day. That is how bugs survive. The right way is a property-based test: generate hundreds of random arrays and assert the two properties that define a correct sort -- the output is ordered, AND the output is a permutation of the input (nothing added, nothing lost, no duplicated-away elements). The slick trick to check both at once: sort a copy with the trusted std.mem.sort, and assert your result equals it element-for-element. Equal-to-a-correct-sort implies both ordered and same-multiset, in one comparison:
fn ascU32(a: u32, b: u32) bool { return a < b; }
fn isSorted(comptime T: type, items: []const T, lessThan: fn (T, T) bool) bool {
var i: usize = 1;
while (i < items.len) : (i += 1) if (lessThan(items[i], items[i - 1])) return false;
return true;
}
test "all four sorts agree with std.mem.sort on random data" {
var prng = std.Random.DefaultPrng.init(0x5EED);
const rand = prng.random();
const gpa = std.testing.allocator;
var round: usize = 0;
while (round < 200) : (round += 1) {
const n = rand.intRangeAtMost(usize, 0, 300);
const original = try gpa.alloc(u32, n);
defer gpa.free(original);
for (original) |*x| x.* = rand.int(u32) % 1000; // lots of duplicates -> stresses ties
const reference = try gpa.dupe(u32, original);
defer gpa.free(reference);
std.mem.sort(u32, reference, {}, std.sort.asc(u32)); // the trusted oracle
const scratch = try gpa.alloc(u32, n);
defer gpa.free(scratch);
inline for (.{ "insertion", "quick", "merge", "heap" }) |name| {
const work = try gpa.dupe(u32, original);
defer gpa.free(work);
if (comptime std.mem.eql(u8, name, "insertion")) insertionSort(u32, work, ascU32);
if (comptime std.mem.eql(u8, name, "quick")) quicksort(u32, work, ascU32);
if (comptime std.mem.eql(u8, name, "merge")) mergeSort(u32, work, scratch, ascU32);
if (comptime std.mem.eql(u8, name, "heap")) heapSort(u32, work, ascU32);
try std.testing.expect(isSorted(u32, work, ascU32));
try std.testing.expectEqualSlices(u32, reference, work); // ordered AND a permutation
}
}
}
I actually run this exact test -- 200 rounds, sizes from 0 to 300, keys mod 1000 so there are plenty of duplicate values to stress the tie handling, all four hand-written sorts checked against the stdlib oracle. It passes, which is the only reason the code above is in this post. Two details worth stealing: the n range includes 0 and 1, because empty and single-element slices are where naive sorts crash (a while (j < items.len - 1) on an empty slice underflows usize -- ask me how I know), and the inline for over string names lets one test body exercise four algorithms without four copies. Because everything runs on std.testing.allocator, a leaked scratch buffer would fail the test outright, exactly as it did for us all through the allocator arc.
In C, the standard tool is qsort(base, count, size, compare) from <stdlib.h> -- and it shows every one of C's tradeoffs. The comparator takes two const void*, so you cast to your type by hand on every call (get it wrong: undefined behaviour), it works in terms of raw byte-sizes so it memcpys elements around blind, and that comparator is a real function pointer the compiler almost never inlines -- so a qsort of ten million ints pays ten-million-ish indirect calls. It is O(n log n) on average but the standard does not even guarantee which algorithm or whether it is stable (glibc's is not). Maximum generality, minimum safety, and a speed ceiling the callback imposes.
In Rust, the split is explicit and honest: slice::sort is stable (a Timsort-style adaptive merge sort, allocates scratch) and slice::sort_unstable is a pattern-defeating quicksort (in-place, faster, no allocation) -- the exact std.mem.sort-versus-std.sort.pdq choice Zig gives you, with the same stable-vs-fast tradeoff. Rust's version leans on the Ord trait for ordering and closures for custom keys (sort_by_key), and the borrow checker guarantees you are not mutating the slice from elsewhere mid-sort. You get memory safety and a clean API; you pay with trait/closure machinery that is mostly zero-cost but occasionally fights you on lifetimes.
In Go, the modern answer is the generic slices.Sort(s) for ordered types and slices.SortFunc(s, cmp) for custom orders (with slices.SortStableFunc when you need stability); the older sort.Slice(x, less) takes a less(i, j int) bool closure over indices and uses reflection-flavoured swaps under the hood, which is why the newer generic slices package is both faster and nicer. Go's sorts are pattern-defeating quicksort variants, unstable unless you pick the stable call. The philosophy is Go's usual one: a small, obvious API in the standard library, no knobs, "it is fast enough, stop thinking about it".
Our Zig versions sit where Zig always sits: the algorithm is a couple dozen lines you can read top to bottom, the comparator is an inlined comptime value with zero call overhead, the element type flows through the generics so mismatches are compile errors, and the choice between stable-and-safe (std.mem.sort) and fast-and-unstable (std.sort.pdq) is explicit and yours. Same four algorithms in every language -- but here you can see all the way down, and pay for exactly what you use ;-)
A stable insertion sort test with a struct. Sort an array of struct { key: u8, seq: usize } by key only, using your insertionSort, where seq records each element's original position. After sorting, assert that within every group of equal keys the seq values are still strictly increasing -- i.e. prove your insertion sort is stable. Then do the same with heapSort and watch the assertion fail, so you see the difference between a stable and an unstable sort in stead of just reading the word.
Turn quicksort into introsort. Add a recursion-depth budget to hybridSort: pass a depth_limit that starts at 2 * log2(n), decrement it on each recursive call, and when it hits zero, sort the current slice with your heapSort in stead of partitioning further. Construct an input that makes the naive last-element-pivot version go quadratic (a sorted array is the classic) and show that your introsort stays fast on it. Argue why the fallback can never make the overall bound worse than O(n log n).
Sort indices, not elements. Write a function that, given items: []const T and a comparator, returns a freshly-allocated []usize of indices ordered so that items[result[0]] is the smallest, items[result[1]] the next, and so on -- an indirect sort that leaves items untouched. Use std.mem.sort over the index slice with a context that carries items, so the comparator reads items[a] and items[b]. This is the pattern you use when the elements are huge (expensive to move) or when you need several orderings of the same data at once.
Look at what sorting quietly unlocks. An unsorted array answers "is this value present?" only by scanning every element -- O(n), no way around it. But a sorted array answers the same question by repeatedly halving the range it could be in, and that is O(log n) -- a million elements found in twenty comparisons in stead of a million. We already leaned on this once: std.sort.lowerBound did exactly that halving on our sorted data, and I slid past it without ceremony:
test "binary search on sorted data" {
var xs = [_]i32{ 2, 4, 6, 8, 10, 12 };
std.mem.sort(i32, &xs, {}, std.sort.asc(i32));
const lb = std.sort.lowerBound(i32, &xs, @as(i32, 7), struct {
fn f(ctx: i32, item: i32) std.math.Order {
return std.math.order(ctx, item);
}
}.f);
try std.testing.expectEqual(@as(usize, 3), lb); // 7 would slot in before 8
}
That twenty-comparisons-in-a-million payoff is one of the highest-leverage ideas in all of programming, and it looks trivial -- until you try to write it correctly and discover the half-dozen ways the boundary conditions bite (off-by-one on the midpoint, the empty range, the "not found" case, finding the first versus the last match, the overflow in (lo + hi) / 2 that has shipped in real libraries for decades). Sorting was the setup. The searching that sorting enables -- and getting every one of those boundary cases provably right -- is where we go next ;-)
Bedankt voor het lezen, en tot de volgende keer!
@scipio