kj::sort_three_way

The speedup scales with how well you know your data and how expensive your comparison function is — and kj::sort_three_way lets you tell it.
Using the hint-enabled version of kj::sort_three_way speed-ups of up to ~3.4x were observed (GCC/libstdc++ on fully sorted data), with expensive-comparison cases and/or choosing the right partitioning technique typically landing in the 1.2x-1.7x range.

A header-only C++23 sorting algorithm that leverages C++20's three-way comparison operator <=>. See the companion blog post — A high-performance sorting algorithm leveraging C++20 three-way comparison — for the story behind it, the measurements and the implementation notes.

Quick start

#include <kj/sort_three_way.hpp>
std::vector<std::wstring> names = /* ... */;
// like std::ranges::sort, but three-way
kj::sort_three_way(names);
// hint: the data is nearly sorted
kj::sort_three_way(kj::sort_with<kj::key_order_nearly_sorted>, names);
// hint: unique keys (no duplicates)
kj::sort_three_way(kj::sort_with<kj::key_distribution_unique>, names);

Requirements

• C++23
• Header-only, no dependencies
• Random-access range
• Comparator returns std::weak_ordering or std::strong_ordering. std::partial_ordering is rejected at the call site by kj::three_way_sortable — sorting requires a total order.

API

Niebloids

namespace kj {
 inline constexpr _sort_three_way_fn sort_three_way;
 inline constexpr _is_sorted_three_way_fn is_sorted_three_way;
}

Overloads

// Range
kj::sort_three_way(rng, cmp = {}, proj = {});
kj::sort_three_way(first, pastEnd, cmp = {}, proj = {});
// Same, with a compile-time sort hint
kj::sort_three_way(kj::sort_with<hints>, rng, cmp = {}, proj = {});
kj::sort_three_way(kj::sort_with<hints>, first, pastEnd, cmp = {}, proj = {});

Defaults: cmp = std::compare_three_way{}, proj = std::identity{}.

Sort hints

kj::sort_hints is an aggregate; kj::sort_with<...> turns it into a compile-time tag. complex_comparison and high_move_cost are inferred from the comparator and value type when left at -1.

struct sort_hints {
 key_distribution distribution = key_distribution_unspecified; // unique | duplicate_heavy
 key_order order = key_order_unspecified; // already_sorted | nearly_sorted | reverse_sorted
 signed char complex_comparison = -1; // inferred if -1
 signed char high_move_cost = -1; // inferred from std::is_trivially_move_constructible_v
 _sort_like _like = _sort_like_unspecified; // test-only: mimic a specific stdlib strategy
};

Shorthand forms for single-hint calls:

kj::sort_with<kj::sort_hints{.distribution = kj::key_distribution_duplicate_heavy}> // full aggregate
kj::sort_with<kj::key_distribution_duplicate_heavy> // equivalent shorthand
kj::sort_with<kj::key_order_nearly_sorted> // equivalent shorthand

Custom comparators and projections

// Custom three-way comparator
auto cmp = [](const T& a, const T& b) -> std::weak_ordering {
 return a.value <=> b.value;
};
kj::sort_three_way(data, cmp);
// Projection
struct Person { std::wstring name; int age; };
kj::sort_three_way(people, std::compare_three_way{}, &Person::name);
// Locale-aware, case-insensitive (Windows)
kj::sort_three_way(strings, [](const std::wstring& a, const std::wstring& b) {
 int result = CompareStringEx(LOCALE_NAME_USER_DEFAULT, LINGUISTIC_IGNORECASE,
 a.c_str(), -1, b.c_str(), -1, nullptr, nullptr, 0);
 return (result - 2) <=> 0;
});

Concept

template<class It, class Compare3Way, class Proj>
concept three_way_sortable =
 std::permutable<It> &&
 indirect_strict_weak_ordering<Compare3Way, std::projected<It, Proj>>;

is_sorted_three_way

Sibling niebloid. Accepts the same three-way comparator shape and forwards to std::ranges::is_sorted.

Characteristics

• Time: O(n log n) worst-case. Introsort falls back to heapsort at depth 1.5·⌊log2(n)⌋ (matching Microsoft STL's choice).
• Space: O(log n) auxiliary.
• Not stable — use std::ranges::stable_sort if stability is required.
• Random-access only.

Building

Header-only. Point your compiler at include/:

# MSVC
cl /std:c++latest /O2 /EHsc /I include ...
# GCC / Clang
g++ -std=c++23 -O3 -I include ...
clang++ -std=c++23 -O3 -I include ...

Or via CMake:

cmake -S . -B build
cmake --build build
ctest --test-dir build

Real-world fixtures

The benchmarks include data captured from Windows SCM (services, nearly sorted by name) and PDH counters (process list, highly clustered, many duplicate parent PIDs). These mirror the kind of systems-software domain where the algorithm was validated — for instance, service management and process-tree resource monitoring in FireDaemon Pro.

License

Boost Software License 1.0 — see LICENSE.

Related

• Companion blog post: A high-performance sorting algorithm leveraging C++20 three-way comparison.
• kj-cpp (broader utilities library): https://gitlab.com/trueqbit/kj-cpp.
• Issues and discussion: https://codeberg.org/trueqbit/three-way-sort/issues.