Sorting
From comparison sorts to SIMD-accelerated radix. Performance is measured, not assumed.
Algorithms
This module treats algorithms as executable claims. Every entry below links to runnable code, benchmark evidence, or reproducible experiments in this repository.
Algorithm Map
Hashing
Hash functions and hash table layouts that survive cache pressure and concurrent access.
Complexity Quick Reference
| Algorithm | Time | Space | Cache Friendly | Parallel | Key Trade-off |
|---|---|---|---|---|---|
| Quicksort (introspective) | O(n log n) avg | O(log n) | Partial | Hard | Branch misprediction on pivot |
| Merge sort | O(n log n) | O(n) | Yes | Easy | Extra memory for merging |
| Radix sort (LSD) | O(nk) | O(n + r) | Yes | Moderate | Key width and digit size |
| Robin Hood hashing | O(1) exp | O(n) | Yes | Hard | Robin Hood shift on insert |
| Swiss Tables (F14) | O(1) exp | O(n) | Yes | Hard | SIMD probing, flat layout |
What makes an algorithm "high-performance" here
- Measurable first. A claim about complexity or throughput must be backed by a benchmark that compiles with the repository's CMake presets.
- Cache-aware, not just big-O aware. Constant factors and memory access patterns often dominate asymptotic bounds on real hardware.
- ISA-conscious. When vectorization changes the algorithmic approach (e.g., bitonic sort on SIMD, SIMD probing in F14), the implementation is inspected with Compiler Explorer and validated with
perf stat. - Maintainability boundary. The repository stops before becoming a production library. Each algorithm is a teaching-sized implementation with explicit trade-off notes, not an exhaustive optimization catalog.
Reading order
- Start with Sorting if you want to see how classic algorithms are adapted for modern CPU pipelines.
- Continue with Hashing to understand memory layout decisions that affect every hash-heavy workload.
- Cross-reference the Performance Methodology page whenever a benchmark claim needs calibration.