brainsort
version 0.5.0stable sortheader-only C++20A stable sorting algorithm for keys that map to an ordered integer: numbers, strings, dates, ids. This page is the C++ library: measured against the stable sorts that ship in today's C++ standard libraries and in the common libraries, on the same inputs, the same compiler flags and the same machines. The Rust crate has its own page with the same sections, built from its own measurements.
Use it
Copy the single header into your project, or add include/ to your include path and include brainsort/brainsort.hpp. Header-only C++20, MIT licensed. GCC, Clang, MSVC and Apple Clang; x86-64 with AVX2 and BMI2 chosen at run time, ARM64 and 32-bit x86 with the same code minus the vector paths.
#include "brainsort.hpp"
std::vector<int> v = ...;
brainsort::sort(v); // stable, by value
brainsort::sort(v.begin(), v.end()); // any random-access range
brainsort::sort(rows, [](const Row& r) { return r.id; }); // by a key
brainsort::sort(rows, [](const Row& r) { return std::pair(r.group, brainsort::desc(r.score)); });
brainsort::sort(rows, [](const Row& a, const Row& b) { return a.name < b.name; }); // a comparator: merge sortAny integer, bool, character type, float, double, enum, pointer, std::string, std::string_view, C string, std::chrono duration or time point, a std::pair, std::tuple or std::array of those, or brainsort::desc(key) for a reversed order. Your own key type takes a brainsort::key_traits specialisation.
Anything move-assignable, in any random-access range: std::vector, std::deque, std::array, std::span, C arrays, pointer pairs. The keys are sorted first, then the elements are permuted once. Every overload is stable.
It uses memory: about 1.5 small records per element while sorting, plus one element per element for the final permutation of plain structs, and it keeps up to 32 MiB of freed blocks for the next call (brainsort::release_memory() frees them). An arbitrary comparator gets a comparison sort, the library's own stable merge sort, without the radix wins. A range of 232 elements or more goes to std::stable_sort.
The full contract, every overload and how the elements are handled: README, The library; step by step with examples: the C++ usage guide.
At a glance
Why these sorts. An opponent has to offer what brainsort offers, so that a win or a loss means something: it is stable, it sorts every key type on this page and it takes an arbitrary comparator. And it is the upstream code as it ships, never a port written here. That is std::stable_sort, cpp-TimSort and Boost.Sort's spinsort and flat_stable_sort; std::sort, pdqsort and the radix libraries are unstable or sort scalar keys only, an easier job, and are not opponents.
How to read this page
Six things to know, then every number below makes sense.
One key type on one input pattern at one size. In every cell brainsort is compared with the best of the other sorts shown, whichever that is. 38 of 45 means brainsort is best or tied in 38 cells.
On every number here: fewer bytes moved, fewer comparisons, less memory, less time.
deterministic numbers describe what an algorithm does: bytes moved, comparisons made, memory asked for. Counted, the same on every machine, held by the test suite. measured numbers are clocks and hardware counters: they depend on the machine and vary between runs, so they are shown per machine.
Every sort on this page is stable (it keeps equal keys in their original order, which sorting records by one field needs), sorts every key type shown and takes an arbitrary comparator, and every one is upstream code run as shipped. A sort that does less (an unstable sort, a radix sort for scalar keys only) has an easier job and is not an opponent; a port written here could be slower than the original and is not one either.
Every number exists at several input sizes. The size control changes the whole page; the across sizes charts show a metric per element as the input grows.
Blue: brainsort ahead. Red: behind. Grey: a tie within 5%. Darker is a larger margin. In charts:
What each algorithm does deterministic
These numbers are the same on every computer. They are counted, not timed: how many bytes an algorithm moves, how many comparisons it makes, how much memory it asks for. Choose a metric:
Where brainsort wins and loses
Across sizes
One cell in detail
Full tables for this metric
Per machineMeasured time per machine measured
Where brainsort wins and loses
Across sizes
One cell in detail
Full tables for this metric
All machines side by side
What a user getsThe library on plain vectors measured
All machines side by side
C++ and Rust on the same machine
Method
How the numbers are made
- Every (size, key type, input, algorithm) cell runs in a fresh process, pinned to one CPU where the OS allows it, so heap state and memory figures do not depend on what ran before.
- The input comes from a fixed seed and is the same for every algorithm. Every element carries its original position, so the harness can check the result: keys in order, no element lost or duplicated, and for a stable sort the exact order of equal keys.
- Deterministic numbers come from one run of an instrumented build that counts every element read and write, every comparison, every table access and every allocation, and feeds the access sequence to a fixed cache model. The upstream code is counted through an element wrapper with the same definitions, so a swap is two reads and two writes for everyone, and through the global allocator (and, for Boost.Sort, its malloc calls) for scratch memory.
- Measured numbers come from repeated timed runs of the plain build: the median of the repetitions, and the best median of two rounds over the whole matrix, because interference can only make a run slower. Below 100,000 elements the timed region sorts enough independent copies to reach 100,000 elements and reports the time per sort, so the clock's own cost stays small. Above, the repetitions shrink in proportion, never below three.
- All algorithms are compiled with the same flags (
-O2, no-march=native). brainsort chooses its AVX2 and BMI2 paths at run time. - The library on plain vectors is a separate benchmark:
brainsort::sorton astd::vectoragainststd::stable_sort, cpp-TimSort and the two Boost.Sort stable sorts on the same generated inputs, the median of a few runs, every result checked, the same flags as above. - Every timing file carries a fingerprint of the code it measured. This page is built from the current sources; a file that measured other code is left out, so no time on this page describes older code than the numbers next to it.
Reproduce it
sh scripts/counts.sh # the deterministic numbers (results/counts.csv, any machine)
sh scripts/bench.sh # the timing of this machine, then both pages of the website
python3 scripts/website.py # the website alone, from results/Windows: scripts\counts.ps1, scripts\bench.ps1. Details in setup.md.
What each metric means
The algorithms
"Best opponent" on this page means the best of the other sorts in a cell. Every sort here is upstream code run as shipped, counted through an element wrapper and the allocator; nothing is a port written here. The pool is the C++ sorts that can do what brainsort does: stable, every key type, an arbitrary comparator. std::sort, pdqsort and the radix libraries are not in it, because an unstable sort or a scalar-only radix sort has an easier job, so a comparison with them would not be like for like. Rust 1.81+ ships driftsort and CPython 3.11+ merges with powersort; the Rust page counts driftsort as shipped, on what a Rust program can observe.
The key types
The inputs
All numbers
Every value behind this page, for the selected size and key types: the deterministic columns once, the measured columns per machine. Open a cell to render it.