Fast Branchless Quicksort using Sorting-Networks with C++ Interface
On modern CPUs, avoiding branch misprediction is a key technique to speed up programs: When ‘if’ slows you down, avoid it.
Performance results naturally depend on the underlying hardware. The following benchmarks show the execution times for sorting 50 million doubles using different sorting implementations. The measurements were taken on an Apple M1 system using Clang and on an AMD Ryzen 3 system using GCC, both compiled with the -O3 option.
| Implementation | Apple M1 | AMD Ryzen |
|---|---|---|
| std::sort | 1.33s | 5.56s |
| pdqsort | 1.33s | 2.81s |
| blqsort | 1.01s | 2.06s |
blqsort
Full source code is included on the page in scrollable blocks and on Github.
This paper by Edelkamp and A. Weiß shows how partitioning performance in Quicksort can be improved by avoiding conditional branches.
The strategy of using an auxiliary buffer for branchless partitioning is inspired by fluxsort. The “auxiliary buffer” here means a 512‑element stack array, not heap memory.
To avoid the O(n²) runtime caused by bad input data, the program can group identical elements together and switch to heapsort for that specific part if it detects a big imbalance during partitioning. The program also checks if a partition is already sorted.
For larger parts, it uses a median-of-medians strategy to find a good pivot. In addition, critical partitioning loops are explicitly unrolled.
For 2 to 12 elements, the algorithm uses custom sorting networks. This approach requires a separate code path for each size but sorts small subsets with very few swaps using a branchless sort‑2 primitive. Source for sorting networks
As a result, blqsort becomes faster than, for example, std::sort and pdqsort for random numbers.
For types with higher copy or move costs (such as strings), the buffer-based branchless approach becomes less efficient. In this case, a BlockQuicksort variant is used, where only element indices are processed branchlessly, and the actual data is moved using fewer swap operations.
blqs.h
// SPDX-License-Identifier: MIT
// blqs.h - Branchless Quicksort
// (c) 2026 christof.kaser@gmail.com
//
// Fast generic sorting for arbitrary types with a C++ interface.
//
// Uses branchless partitioning and sorting networks for
// trivial types and BlockQuicksort (Edelkamp & Weiß) for
// complex types, with a fallback to heapsort.
#ifndef BLQS_H
#define BLQS_H
#include <cstddef>
#include <cstdint>
#include <type_traits>
#include <functional>
#include <utility>
namespace blqs {
template<typename T, typename Compare>
static inline void sort2(T& a, T& b, Compare comp) {
T x = a; T y = b;
bool m = comp(x, y);
a = m ? x : y; b = m ? y : x;
}
template<typename T, typename Compare>
static inline void sort3(T& a, T& b, T& c, Compare comp) {
sort2(a, b, comp); sort2(b, c, comp); sort2(a, b, comp);
}
template<typename T, typename Compare>
static inline void sort4(T& a, T& b, T& c, T& d, Compare comp) {
sort2(a, b, comp); sort2(c, d, comp); sort2(a, c, comp);
sort2(b, d, comp); sort2(b, c, comp);
}
template<typename T, typename Compare>
static inline void sort5(T& a, T& b, T& c, T& d, T& e, Compare comp) {
sort2(b, c, comp); sort2(d, e, comp); sort2(b, d, comp);
sort2(a, c, comp); sort2(a, d, comp); sort2(c, e, comp);
sort2(a, b, comp); sort2(c, d, comp); sort2(b, c, comp);
}
template<typename T, typename Compare>
static inline void sort6(T& a, T& b, T& c, T& d, T& e, T& f, Compare comp) {
sort2(a, b, comp); sort2(c, d, comp); sort2(e, f, comp);
sort2(a, c, comp); sort2(b, d, comp); sort2(e, f, comp);
sort2(a, e, comp); sort2(b, f, comp); sort2(c, e, comp);
sort2(d, f, comp); sort2(b, c, comp); sort2(d, e, comp);
sort2(c, d, comp);
}
template<typename T, typename Compare>
static inline void sort7(T& a, T& b, T& c, T& d, T& e, T& f, T& g, Compare comp) {
sort2(a, g, comp); sort2(c, d, comp); sort2(e, f, comp);
sort2(a, c, comp); sort2(b, e, comp); sort2(d, g, comp);
sort2(a, b, comp); sort2(c, f, comp); sort2(d, e, comp);
sort2(b, c, comp); sort2(e, g, comp);
sort2(c, d, comp); sort2(e, f, comp);
sort2(b, c, comp); sort2(d, e, comp); sort2(f, g, comp);
}
template<typename T, typename Compare>
static inline void sort8(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h, Compare comp) {
sort2(a,b,comp); sort2(c,d,comp); sort2(e,f,comp); sort2(g,h,comp);
sort2(a,c,comp); sort2(b,d,comp); sort2(e,g,comp); sort2(f,h,comp);
sort2(b,c,comp); sort2(f,g,comp);
sort2(a,e,comp); sort2(b,f,comp); sort2(c,g,comp); sort2(d,h,comp);
sort2(c,e,comp); sort2(d,f,comp);
sort2(b,c,comp); sort2(d,e,comp); sort2(f,g,comp);
}
template<typename T, typename Compare>
static inline void sort9(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h, T& i, Compare comp) {
sort2(a,d,comp); sort2(b,h,comp); sort2(c,f,comp); sort2(e,i,comp);
sort2(a,h,comp); sort2(c,e,comp); sort2(d,i,comp); sort2(f,g,comp);
sort2(a,c,comp); sort2(b,d,comp); sort2(e,f,comp); sort2(h,i,comp);
sort2(b,e,comp); sort2(d,g,comp); sort2(f,h,comp);
sort2(a,b,comp); sort2(c,e,comp); sort2(d,f,comp); sort2(g,i,comp);
sort2(c,d,comp); sort2(e,f,comp); sort2(g,h,comp);
sort2(b,c,comp); sort2(d,e,comp); sort2(f,g,comp);
}
template<typename T, typename Compare>
static inline void sort10(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h, T& i, T& j, Compare comp) {
sort2(a,b,comp); sort2(c,f,comp); sort2(d,g,comp); sort2(e,h,comp); sort2(i,j,comp);
sort2(a,g,comp); sort2(b,i,comp); sort2(c,e,comp); sort2(d,j,comp); sort2(f,h,comp);
sort2(a,c,comp); sort2(b,d,comp); sort2(e,f,comp); sort2(g,i,comp); sort2(h,j,comp);
sort2(a,b,comp); sort2(c,h,comp); sort2(d,f,comp); sort2(e,g,comp); sort2(i,j,comp);
sort2(b,c,comp); sort2(d,e,comp); sort2(f,g,comp); sort2(h,i,comp);
sort2(b,d,comp); sort2(c,e,comp); sort2(f,h,comp); sort2(g,i,comp);
sort2(c,d,comp); sort2(e,f,comp); sort2(g,h,comp);
}
template<typename T, typename Compare>
static inline void sort11(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h, T& i, T& j, T& k, Compare comp) {
sort2(a,j,comp); sort2(b,g,comp); sort2(c,e,comp); sort2(d,h,comp); sort2(f,i,comp);
sort2(a,b,comp); sort2(d,f,comp); sort2(e,k,comp); sort2(g,j,comp); sort2(h,i,comp);
sort2(b,d,comp); sort2(c,f,comp); sort2(e,h,comp); sort2(i,k,comp);
sort2(a,e,comp); sort2(b,c,comp); sort2(d,h,comp); sort2(f,j,comp); sort2(g,i,comp);
sort2(a,b,comp); sort2(c,g,comp); sort2(e,f,comp); sort2(h,i,comp);
sort2(j,k,comp);
sort2(c,e,comp); sort2(d,g,comp); sort2(f,h,comp); sort2(i,j,comp);
sort2(b,c,comp); sort2(d,e,comp); sort2(f,g,comp); sort2(h,i,comp);
sort2(c,d,comp); sort2(e,f,comp); sort2(g,h,comp);
}
template<typename T, typename Compare>
static inline void sort12(T& a, T& b, T& c, T& d, T& e, T& f, T& g, T& h, T& i, T& j, T& k, T& l, Compare comp) {
sort2(a,i,comp); sort2(b,h,comp); sort2(c,g,comp); sort2(d,l,comp); sort2(e,k,comp); sort2(f,j,comp);
sort2(a,c,comp); sort2(b,e,comp); sort2(d,f,comp); sort2(g,i,comp); sort2(h,k,comp); sort2(j,l,comp);
sort2(a,b,comp); sort2(c,j,comp); sort2(e,h,comp); sort2(f,g,comp); sort2(k,l,comp);
sort2(b,d,comp); sort2(c,h,comp); sort2(e,j,comp); sort2(i,k,comp);
sort2(a,b,comp); sort2(c,d,comp); sort2(e,f,comp); sort2(g,h,comp); sort2(i,j,comp); sort2(k,l,comp);
sort2(b,c,comp); sort2(d,f,comp); sort2(g,i,comp); sort2(j,k,comp);
sort2(c,e,comp); sort2(d,g,comp); sort2(f,i,comp); sort2(h,j,comp);
sort2(b,c,comp); sort2(d,e,comp); sort2(f,g,comp); sort2(h,i,comp); sort2(j,k,comp);
}
template<typename T, typename Compare>
static inline void sorting_network(T* l, int partsz_min1, Compare comp) {
switch (partsz_min1) {
case 11: sort12(l[0],l[1],l[2],l[3],l[4],l[5],l[6],l[7],l[8],l[9],l[10],l[11],comp); break;
case 10: sort11(l[0],l[1],l[2],l[3],l[4],l[5],l[6],l[7],l[8],l[9],l[10],comp); break;
case 9: sort10(l[0],l[1],l[2],l[3],l[4],l[5],l[6],l[7],l[8],l[9],comp); break;
case 8: sort9(l[0],l[1],l[2],l[3],l[4],l[5],l[6],l[7],l[8],comp); break;
case 7: sort8(l[0],l[1],l[2],l[3],l[4],l[5],l[6],l[7],comp); break;
case 6: sort7(l[0],l[1],l[2],l[3],l[4],l[5],l[6],comp); break;
case 5: sort6(l[0],l[1],l[2],l[3],l[4],l[5],comp); break;
case 4: sort5(l[0],l[1],l[2],l[3],l[4],comp); break;
case 3: sort4(l[0],l[1],l[2],l[3],comp); break;
case 2: sort3(l[0],l[1],l[2],comp); break;
case 1: sort2(l[0], l[1], comp); break;
default: break;
}
}
template<typename T, typename Compare>
void heap_sort(T* left, T* right, Compare comp) {
long n = right - left + 1;
if (n < 2) return;
for (long i = n / 2; ; ) {
T k;
if (i > 0) k = left[--i];
else {
n -= 1; if (n == 0) return;
k = left[n]; left[n] = left[0];
}
long j = i;
while (j * 2 + 1 < n) {
long child = j * 2 + 1;
if (child + 1 < n && comp(left[child], left[child + 1])) child++;
if (!comp(k, left[child])) break;
left[j] = left[child]; j = child;
}
left[j] = k;
}
}
template<typename T, typename Compare>
static inline void med5(T& a, T& b, T& c, T& d, T& e, Compare comp) {
sort2(a, b, comp); sort2(c, d, comp);
sort2(a, c, comp); sort2(b, d, comp);
sort2(b, c, comp); sort2(c, e, comp);
sort2(b, c, comp);
}
constexpr int SMALLPART = 256;
constexpr int SWSZ = 1024;
constexpr int UNROLL = 16;
template<typename T, typename Compare>
static T* partition_small(T* __restrict__ left, T* __restrict__ right, Compare comp) {
T* outerleft = left;
T* pivp = left + (right - left) / 2;
med5(left[1], left[2], *pivp, right[-1], *right, comp);
left += 3; right -= 2;
T piv = *pivp; *pivp = *outerleft;
T swbuf[SMALLPART];
T *sw = swbuf, *lwr = left;
while (left <= right) {
bool h = comp(*left, piv);
*lwr = *sw = *left++;
lwr += h; sw += !h;
}
std::move(swbuf, sw, lwr);
lwr -= 1; *outerleft = *lwr; *lwr = piv;
return lwr;
}
template<typename T, typename Compare>
static T* partition_large(T* __restrict__ left, T* __restrict__ right, Compare comp) {
T* outerleft = left;
T* pivp = left + (right - left) / 2;
med5(left[1], left[2], left[3], left[4], left[5], comp);
med5(left[21], left[22], left[23], left[24], left[25], comp);
med5(pivp[-2], pivp[-1], pivp[0], pivp[1], pivp[2], comp);
med5(right[-14], right[-13], right[-12], right[-11], right[-10], comp);
med5(right[-4], right[-3], right[-2], right[-1], right[0], comp);
med5(left[3], left[23], pivp[0], right[-12], right[-2], comp);
left += 1;
T piv = *pivp; *pivp = *outerleft;
while (comp(*left, piv)) left++;
if (left >= outerleft + 12) {
// could be sorted
*pivp = piv;
for (T* p = outerleft + 1; p <= right; p++) {
if (comp(*p, *(p - 1))) {
*pivp = *outerleft;
goto not_sorted;
}
}
return NULL;
}
not_sorted:
T swbuf[SWSZ];
T *lwr = left, *rwr = right, *sw = swbuf;
while (sw < swbuf + SWSZ - UNROLL && left <= right - UNROLL) {
for (int i = UNROLL; i--;) {
bool h = comp(*right, piv); *rwr = *sw = *right--; rwr -= !h; sw += h;
}
}
while (sw < swbuf + SWSZ - UNROLL && left <= right) {
bool h = comp(*right, piv); *rwr = *sw = *right--; rwr -= !h; sw += h;
}
while (left <= right - UNROLL) {
while (rwr > right + UNROLL && left <= right - UNROLL) {
for (int i = UNROLL; i--;) {
bool h = comp(*left, piv); *lwr = *rwr = *left++; lwr += h; rwr -= !h;
}
}
while (lwr < left - UNROLL && left <= right - UNROLL) {
for (int i = UNROLL; i--;) {
bool h = comp(*right, piv); *rwr = *lwr = *right--; rwr -= !h; lwr += h;
}
}
}
while (rwr > right && left <= right) {
bool h = comp(*left, piv); *lwr = *rwr = *left++; lwr += h; rwr -= !h;
}
while (left <= right) {
bool h = comp(*right, piv); *rwr = *lwr = *right--; rwr -= !h; lwr += h;
}
std::move(swbuf, sw, lwr);
*outerleft = *rwr; *rwr = piv;
return rwr;
}
template<typename T, typename Compare>
void blqsort(T* left, T* right, Compare comp) {
while (1) {
ptrdiff_t partszm1 = right - left;
T* mid;
if (partszm1 <= SMALLPART) {
if (partszm1 <= 11) {
sorting_network(left, (int)partszm1, comp);
return;
}
mid = partition_small(left, right, comp);
}
else {
mid = partition_large(left, right, comp);
if (mid == NULL) return; // already sortiert
if ((mid - left) * 16 < partszm1 || (right - mid) * 16 < partszm1) {
heap_sort(left, mid - 1, comp);
T piv = *mid;
mid += 1;
for (T* p = mid; p <= right; p++) {
if (!comp(piv, *p)) {
std::swap(*mid, *p);
mid++;
}
}
heap_sort(mid, right, comp);
return;
}
}
if (mid - left < right - mid) {
blqsort(left, mid - 1, comp);
left = mid + 1;
} else {
blqsort(mid + 1, right, comp);
right = mid - 1;
}
}
}
template <typename T, typename Compare>
static inline void insert_sort(T* left, T* right, Compare comp) {
for (T* i = left + 1; i <= right; i++) {
T key = std::move(*i);
T* j = i;
while (j > left && comp(key, *(j - 1))) {
*j = std::move(*(j - 1));
j--;
}
*j = std::move(key);
}
}
template <typename T, typename Compare>
static inline void med3(T* a, T* b, T* c, Compare comp) {
if (comp(*b, *a)) std::swap(*a, *b);
if (comp(*c, *a)) std::swap(*a, *c);
if (comp(*c, *b)) std::swap(*b, *c);
}
// Based on BlockQuicksort by Edelkamp and Weiß
template <typename T, typename Compare>
void block_qsort(T* left0, T* right0, Compare comp) {
constexpr long BLSZ = 512;
while (right0 - left0 > 16) {
size_t sizem1 = right0 - left0;
T* mid = left0 + sizem1 / 2;
T* left = left0 + 1;
T* right = right0;
if (sizem1 > 64) {
med3(left, left + 1, left + 2, comp);
med3(mid - 1, mid, mid + 1, comp);
med3(right - 2, right - 1, right, comp);
med3(left + 1, mid, right - 1, comp);
}
else {
med3(left, mid, right, comp);
left += 1;
right -= 1;
}
T pivot = std::move(*mid);
*mid = std::move(*left0);
T* left_p[BLSZ];
T* right_p[BLSZ];
int nleft = 0;
int nright = 0;
int left_offs, right_offs;
while (right >= left) {
int blsz = std::min(BLSZ, right - left + 1);
if (nleft == 0) {
for (T* endl = left + blsz; left < endl; left++) {
left_p[nleft] = left;
nleft += !comp(*left, pivot);
}
left_offs = 0;
}
else {
for (T* endr = right - blsz; right > endr; right--) {
right_p[nright] = right;
nright += !comp(pivot, *right);
}
right_offs = 0;
}
int nswaps = std::min(nleft, nright);
for (int k = 0; k < nswaps; k++) {
std::iter_swap(left_p[left_offs], right_p[right_offs]);
left_offs++;
right_offs++;
}
nleft -= nswaps;
nright -= nswaps;
}
if (nleft) {
for (int k = left_offs + nleft - 1; k >= left_offs; k--, right--) {
std::iter_swap(left_p[k], right);
}
}
else {
for (int k = right_offs + nright - 1; k >= right_offs; k--, left++) {
std::iter_swap(right_p[k], left);
}
right = left - 1;
}
*left0 = std::move(*right);
*right = std::move(pivot);
ptrdiff_t szl = right - left0;
ptrdiff_t szr = right0 - right;
ptrdiff_t szmin = (szl < szr) ? szl : szr;
if (szmin * 16 < right0 - left0) {
heap_sort(left0, right - 1, comp);
heap_sort(right + 1, right0, comp);
return;
}
if (szl < szr) {
block_qsort(left0, right - 1, comp);
left0 = right + 1;
} else {
block_qsort(right + 1, right0, comp);
right0 = right - 1;
}
}
insert_sort(left0, right0, comp);
}
template <typename T, typename Compare = std::less<T>>
void sort(T* first, T* last, Compare comp = Compare()) {
if (last - first < 2) return;
constexpr bool copy_is_cheap =
std::is_trivially_copyable<T>::value && sizeof(T) <= 16;
if constexpr (copy_is_cheap) {
blqsort(first, last - 1, comp);
}
else {
block_qsort(first, last - 1, comp);
}
}
}
#endif
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include "blqs.h"
constexpr int SIZE = 50000000;
double data[SIZE];
double cputime() {
return (double)clock() / CLOCKS_PER_SEC;
}
int main() {
double t0;
printf("blqs::sort - sorting %d million doubles ...\n", SIZE / 1000000);
for (int i = 0; i < SIZE; i++) data[i] = rand() / 1024.0;
t0 = cputime();
blqs::sort(data, data + SIZE);
printf("Random: %.2fs\n", cputime() - t0);
t0 = cputime();
blqs::sort(data, data + SIZE);
printf("Sorted: %.2fs\n", cputime() - t0);
for (int i = 0; i < 10; i++) std::swap(data[rand() % (SIZE / 10)], data[rand() % (SIZE / 10)]);
t0 = cputime();
blqs::sort(data, data + SIZE);
printf("Nearly sorted: %.2fs\n", cputime() - t0);
for (int i = 0; i < SIZE; i++) data[i] = rand() % 1000;
t0 = cputime();
blqs::sort(data, data + SIZE);
printf("Duplicates: %.2fs\n", cputime() - t0);
}
g++ -std=c++17 -O3 test.cpp && ./a.out
blqsort - sorting 50 million doubles ...
Random: 1.01s
Sorted: 0.03s
Nearly sorted: 0.13s
Duplicates: 0.51s
std::sort - sorting 50 million doubles ...
Random: 1.33s
Sorted: 0.05s
Nearly sorted: 0.07s
Duplicates: 0.28s
Sorting Custom Data Structures
In practice, we often need to sort custom data structures. This is where SIMD libraries like Google Highway - while very fast for simple numbers - become difficult to use.
Using std::sort or blqs::sort gives you much more flexibility;
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include "blqs.h"
constexpr int SIZE = 50000000;
struct entry {
int32_t id;
int32_t value;
bool operator<(const entry& other) const {
return id < other.id;
}
};
struct entry data[SIZE];
double cputime() {
return (double)clock() / CLOCKS_PER_SEC;
}
int main() {
double t0;
printf("blqs::sort - sorting %d million structs ...\n", SIZE / 1000000);
for (int i = 0; i < SIZE; i++) data[i].id = rand();
t0 = cputime();
blqs::sort(data, data + SIZE);
printf("Time: %.2fs\n", cputime() - t0);
}
structs.
| Implementation | Apple M1 | AMD Ryzen |
|---|---|---|
| std::sort | 3.46s | 4.75s |
| pdqsort | 3.46s | 4.72s |
| blqsort | 0.97s | 2.20s |
christof.kaser@gmail.com