Modern Sorting Algorithm Libraries: pdqsort vs quadsort vs ips4o vs glidesort Compared

Beyond std::sort: Why Modern Sorting Libraries Matter

The standard library sorting functions in C, C++, and Rust have served reliably for decades. But algorithm research didn’t stop in the 1990s. Modern sorting libraries exploit branch prediction, SIMD instructions, cache locality, and multi-core parallelism in ways that std::sort and qsort never could.

The difference is striking in practice. On random integer arrays, pdqsort (pattern-defeating quicksort) is 2-3x faster than C++ std::sort. On pre-sorted data with small perturbations, the gap widens to 5x or more. For systems that sort millions of items — database query engines, ETL pipelines, log processors — upgrading the sorting algorithm alone can reduce query latency by double-digit percentages.

For related performance topics, see our server benchmarking guide and storage benchmarking comparison. For code quality practices, our code quality platforms comparison covers complementary static analysis tools.

Comparison Table

pdqsort: Pattern-Defeating Quicksort

pdqsort (2,497 stars) by Orson Peters is one of the most influential sorting algorithm papers-turned-implementation of the last decade. It’s a single C++ header file (pdqsort.h) that you can drop into any project and use as a direct replacement for std::sort — with the same API and guaranteed O(n log n) worst case.

The key innovation is “pattern-defeating”: pdqsort detects when quicksort’s pivot selection is performing poorly (the input has patterns that foil naive pivoting) and dynamically switches strategies. For nearly-sorted data, it runs in O(n). It also detects when it’s fallen into quicksort’s worst case and heapsorts the remaining partition.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include "pdqsort.h"
#include <vector>
#include <iostream>

int main() {
    std::vector<int> data = {42, 7, 19, 3, 88, 15, 23, 1, 56};
    
    // Drop-in replacement for std::sort
    pdqsort(data.begin(), data.end());
    
    for (int x : data) std::cout << x << " ";
    // Output: 1 3 7 15 19 23 42 56 88
    
    return 0;
}

Performance profile: On random data, pdqsort is roughly 2x faster than std::sort (libstdc++). On “mostly sorted” data (10% random perturbations), it’s ~5x faster. On pre-sorted data, it’s nearly instant (O(n) branchless copy). This makes it ideal for systems that re-sort incrementally modified collections — database materialized views, live leaderboards, and rebalancing operations.

quadsort: Branchless Mergesort for the Modern Era

quadsort (2,199 stars) by Igor van den Hoven is a stable, adaptive mergesort written in a single C file. Its name comes from the “quad” exchange — it sorts groups of four elements using a sorting network before merging, which ensures every comparison is branchless.

Branchless sorting means the CPU never mispredicts a conditional jump during comparison. On modern processors where branch misprediction costs 15-20 cycles, this matters enormously. quadsort’s merge phase is also partially unrolled to maintain instruction-level parallelism.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include "quadsort.h"
#include <stdio.h>

int main() {
    int data[] = {42, 7, 19, 3, 88, 15, 23, 1, 56};
    size_t n = sizeof(data) / sizeof(data[0]);
    
    quadsort(data, n);
    
    for (size_t i = 0; i < n; i++)
        printf("%d ", data[i]);
    // Output: 1 3 7 15 19 23 42 56 88
    
    return 0;
}

Key advantage — stability: quadsort is stable (equal elements preserve their original relative order), which pdqsort is not. This is critical when sorting database rows by a secondary key — you want rows with equal primary keys to maintain their insertion order. If your sorting pipeline requires stability, quadsort or glidesort are the better choices.

Performance profile: On random data, quadsort is 30-50% faster than qsort. On pre-sorted or reverse-sorted data, it’s 3-5x faster. It handles arrays with long runs of equal elements particularly well — ideal for sorting data with low cardinality columns.

ips4o: Parallel Sample Sort for Multi-Core

ips4o (168 stars) — In-place Parallel Super Scalar Samplesort — addresses the elephant in the room: most sorting algorithms use a single core. On a 64-core server, sorting a billion integers with std::sort wastes 63 cores entirely.

ips4o is the first practical in-place parallel sorting algorithm. Traditional parallel sorts (like GNU parallel sort) require O(n) auxiliary memory per thread. ips4o needs only O(k log n) extra space where k is the oversampling factor, making it usable on memory-constrained systems. The “in-place” property means it doesn’t allocate temporary buffers proportional to the input size.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include "ips4o.hpp"
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> data(100'000'000);
    std::generate(data.begin(), data.end(), rand);
    
    // Sort using all available cores
    ips4o::parallel::sort(data.begin(), data.end());
    
    return 0;
}

Performance profile: On 16 cores, ips4o achieves ~12x speedup over single-threaded std::sort. The parallel efficiency is ~75-80%, which is exceptional for sorting algorithms. Use cases include ETL pipeline stages, database index builds, and any batch processing that involves a sort phase on multi-core servers.

glidesort: Rust’s Sorting Evolution

glidesort by Lukas Bergdoll (part of the sort-research-rs project, 537 stars) is a stable, adaptive sorting algorithm designed for Rust. It combines the best ideas from pdqsort (pattern detection), quadsort (branchless comparisons), and Timsort (natural run detection) into a hybrid algorithm tuned for both random and partially ordered data.

glidesort is notable for being both stable AND adaptive — a combination that’s surprisingly rare. Timsort (Java, Python) is stable and adaptive for nearly-sorted data but falls back to O(n log n) for random. pdqsort is adaptive but unstable. glidesort aims to be both.

1
2
3
4
5
6
7
8

// Cargo.toml: glidesort = "0.1"
use glidesort::sort;

fn main() {
    let mut data = vec![42, 7, 19, 3, 88, 15];
    sort(&mut data);
    println!("{:?}", data); // [3, 7, 15, 19, 42, 88]
}

Key features: Stable sorting guarantees, branchless comparisons via sorting networks, pattern detection from pdqsort, natural run merging from Timsort, and SIMD-aware memory operations. glidesort also handles “mostly sorted with outliers” exceptionally well — the worst case for vanilla quicksort.

Practical Selection Guide

Integration Tips for Production Systems

Header-only integration (pdqsort, ips4o): Copy the single header file into your project and include it. No build system changes needed. This simplicity makes these libraries ideal for organizations with strict dependency policies.

Build system integration (glidesort via Cargo): Add one line to Cargo.toml and glidesort is available project-wide. For larger Rust projects, benchmark against the standard library sort for your specific data patterns — glidesort’s advantage is most pronounced on partially ordered data.

Gradual adoption: You don’t need to replace every sort() call at once. Start with the hot path — the sort that shows up in your profiling traces. Replace that one call, run your benchmarks, and expand from there. The API compatibility of pdqsort with std::sort makes this a one-line change.

FAQ

Can I use pdqsort as a direct replacement for std::sort?

Yes. pdqsort implements the same iterator-based interface as std::sort(begin, end). It also supports custom comparators: pdqsort(begin, end, std::greater<int>()). The only difference is guaranteed O(n log n) worst case, whereas std::sort technically allows O(n²) in pathological cases (though modern implementations avoid this).

Why would I need a stable sort?

Stability matters when sorting by multiple keys in sequence. If you sort a table of employees by department, then by salary, a stable sort ensures employees within the same salary band remain sorted by department. Unstable sorts (like pdqsort or std::sort) may scramble the department ordering within equal salary groups. Use quadsort or glidesort when stability matters.

Are these libraries faster than GPU-based sorting?

For datasets that fit in GPU memory and are already on the GPU, a GPU radix sort (like CUB’s DeviceRadixSort) can be faster. However, the PCIe transfer cost to move data to/from GPU memory typically eliminates the advantage unless the data is already GPU-resident. For CPU-resident data, pdqsort and ips4o are the better choices.

How do I benchmark sorting performance for my specific data?

Write a simple benchmark that calls the sort on a representative sample of your data. Use Google Benchmark or Criterion.rs for statistically rigorous measurements. Test multiple data distributions: random, nearly sorted (5% perturbation), reverse sorted, and all-equal. Each algorithm has different strengths — your specific data pattern determines which one wins.

💰 想测试你的市场判断力？我用 Polymarket 做预测市场交易——这是全球最大的预测市场平台，从大选结果到技术监管时间线，什么都可以押注。和赌博不同，这是真正的信息市场：你懂的信息越多，胜率越高。我靠预测技术相关事件的走向已经赚了不少。用我的邀请链接注册：Polymarket.com