NovaSort

NovaSort is a header-only C++20 sorting routine built around an adaptive hybrid strategy. It combines introsort-style partitioning with natural-run detection and merge paths for inputs that already contain useful order.

The public API is intentionally small: include novasort.h and call nova_sort(begin, end, cmp).

Quick Start

Add include/ to your include path:

#include "novasort.h"

#include <vector>

std::vector<int> data = {3, 1, 4, 1, 5, 9, 2, 6};
nova_sort(data.begin(), data.end());

Compile with C++20 enabled:

g++ -O3 -march=native -std=c++20 your_source.cpp -Iinclude

API

template <typename Iter, typename Cmp = std::less<>>
void nova_sort(Iter begin, Iter end, Cmp cmp = Cmp{});

• Iter must be a random-access iterator.
• Cmp is a strict weak ordering; it defaults to std::less<>.
• The sort is not stable.
• Some merge paths allocate temporary storage; allocation failure is propagated.

Complexity

Best	Average	Worst	Extra memory
O(n)	O(n log n)	O(n log n)	O(n) when merging

Build And Test

This repository uses CMake and C++20.

cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --config Release

The build produces two test-oriented executables:

• stress: fuzzing, operation-count probes, and large-input stress checks.
• benchmark: comparisons against the reference sorts in third_party/.

Example benchmark runs:

build/Release/benchmark.exe --no-throughput
build/Release/benchmark.exe --quick

On single-config generators, the executables may be under build/ instead of build/Release/.

Implementation Notes

NovaSort keeps the public surface small, but the single-header implementation has two main layers:

• the top-level nova_sort entry point performs lightweight input classification;
• the introsort loop handles the general unstructured case.

At a high level, inputs are routed as follows:

Input shape	Main path
Very small ranges	Fixed sorting networks
Short ranges	Quick structure check, then introsort if needed
Already sorted, reversed, or equal ranges	Return or normalize with minimal work
Few useful natural runs	Natural merge over collected run bounds
Many structured runs	Internal TimSort-style merge
One large run plus a noisy head or tail	Sort the noisy side, then merge
Random or unstructured data	Introsort-style partitioning with heapsort fallback

The merge paths use galloping when one run keeps winning comparisons. The general sorting path uses pivot selection, branch-conscious block partitioning, partial insertion checks, and pattern-breaking swaps for poor partitions.

Most implementation details live in the novasort_detail namespace inside include/novasort.h; the public API remains the single nova_sort function.

Sorting Visualization

Animated trace from the companion local visualizer:

Benchmarks

The benchmark suite compares nova_sort with std::sort, pdqsort, and timsort across a range of generated input patterns and sizes. It also includes complex-object tests, operation-count probes, and optional large-throughput runs.

For regular local checks, prefer:

build/Release/benchmark.exe --no-throughput

Use --quick for a shorter smoke run.

The README charts below are snapshot visuals rendered from a Linux / GCC 11.4.0 benchmark export. Re-run the benchmark on your target hardware for direct comparisons.

Third-Party Reference Implementations

third_party/ contains reference sort implementations used only by the benchmark:

• pdqsort - Pattern-defeating quicksort (zlib License)
• timsort.hpp - C++ TimSort port (MIT)

NovaSort's implementation also adapts techniques from pdqsort, cpp-TimSort, driftsort, and ipnsort. See THIRD_PARTY_NOTICES.md for attribution and license notices.

License

NovaSort's original code is licensed under the MIT License. See LICENSE for details. Third-party reference headers and adapted implementation sources retain their respective licenses; see THIRD_PARTY_NOTICES.md.