Smoothsort in Zig

Plebosaur · January 21, 2026, 2:22am

gist.github.com

https://gist.github.com/OrfeasPliaridis/0c1c4473bda5b30bfef36f3423b27e0f

assSort7.zig

// AssSort7 (Assumption smoothsort) makes a few performance improvements over most smoothsort implementations:
// For each node with children, its right child is not less than its left. Assuming this assumption saves more CPU cycles than it takes to maintain it.
// We manually process edge cases for nodes that don't have children / neighbors. This saves us checks inside the while loops.
// We make the code more branchless for the bit manipulations.
// In our array we store leonardo numbers multiplied by the size of T, so we don't have to do a multiplication for pointer arithmetic. Relevant when T is not a power of 2.

fn LeonardoArrWrapperStruct(comptime typeSize: usize) type {
    if (typeSize == 0) @compileError("Error, size must be greater than 0");

    //The maximum leonardonumber we can hit without overflowing.

This file has been truncated. show original

learnSmoothsort.zig

//Readable unoptimized smoothsort implementation for educational purposes.

const std = @import("std");
const T = i32;

// Calculates leonardo Number.
// They are defined similar to the fibonacci numbers.
// Fibonacci: f(0), f(1) = 1 then for n > 1 f(n) = f(n-1) + f(n-2)
// Leonardo: l(0), l(1) = 1 then for n > 1 l(n) = l(n-1) + l(n-2) + 1

This file has been truncated. show original

Smoothsort is a sorting algorithm with:

No recursion
O(1) memory
In place
Adaptive (O(N) for near sorted arrays)
O(NlogN) worse case

It’s the best sorting algorithm I found when you don’t want to allocate memory, you don’t want recursion, but you can expect your input to be relatively sorted, meaning that heapsort doing guaranteed O(NlogN) is not desirable. It was developed by dijkstra for that very reason.

The algorithm is also used in musl libc:

I have provided 2 implementations, an optimized one and one that I tried to make very readable. You should be able to understand the readable one if you do a small amount of research on the algorithm. If people are interested in it, I could do a tutorial because I didn’t find much in terms of good learning resources when I was implementing it.

The optimized one, I started calling assSort (assumption smoothsort) because I made some changes in the core logic of the algorithm to boost performance. The one I am sharing with you (assSort7) is about 20% slower than std heapsort on a random array in the benchmarks I ran. I still have some optimizations I want to try on it.