23 sorting algorithms written from scratch in C11. Includes a benchmark and race tool.
include/sorts.h shared type definitions and function declarations
src/comparison/ comparison-based sorts (15)
src/distribution/ non-comparison sorts (4)
src/novelty/ educational / esoteric sorts (4)
search/ binary and linear search
bench/bench.c benchmark, race, and sweep tool
| name | complexity | stable | notes |
|---|---|---|---|
| bubble | O(n^2) | yes | early-exit on sorted input |
| cocktail | O(n^2) | yes | bidirectional bubble |
| comb | O(n^2) | no | shrinking gap; faster than bubble |
| gnome | O(n^2) | yes | |
| heap | O(n log n) | no | in-place; poor cache behaviour |
| insertion | O(n^2) | yes | fast on small/nearly-sorted data |
| introsort | O(n log n) | no | C++ std::sort: quick+heap+insert |
| merge | O(n log n) | yes | O(n) auxiliary space |
| oddeven | O(n^2) | yes | parallel-friendly sorting network |
| pancake | O(n^2) | no | prefix-flip operations only |
| quick | O(n log n) avg | no | median-of-3; tail-call optimized |
| selection | O(n^2) | no | O(n) writes; good for EEPROM |
| shell | O(n log n) | no | Ciura (2001) gap sequence |
| stooge | O(n^2.71) | no | strictly educational |
| timsort | O(n log n) | yes | Python/Java: natural-run merge |
| counting | O(n+k) | yes | optimal when range k = O(n) |
| lsd_radix | O(d*n) | yes | byte-at-a-time; 4 passes |
| msd_radix | O(d*n) | no | recursive; early termination |
| pigeonhole | O(n+k) | yes | counting sort with value buckets |
| bitonic | O(n log^2 n) | no | sorting network; GPU-native |
| bogo | O((n+1)!) | no | do not use (capped at n=10) |
| cycle | O(n^2) | no | minimum array writes |
| postman | O(d*n) | no | base-10 MSD radix; non-negative |
make all # bench + standalone demos + search tools
make bench # benchmark tool only
make demos # standalone demo binaries
make cleanRequires gcc with C11 support. Links -lm and -lpthread.
Each sort compiles to its own binary, generates random data, and prints before/after:
src/comparison/quick
src/distribution/lsd_radix
src/novelty/cycle
search/binarybench list
bench run <algo> <n> [seed]
bench race <algo1> <algo2> <n> [seed]
bench sweep <algo> <max_n> [steps]
race runs both algorithms in parallel on identical data with a live two-line display,
then prints a bar chart. sweep shows scaling behaviour across geometrically spaced sizes.
Both use a live spinner when stdout is a tty.
bench/bench race quick merge 500000
bench/bench race lsd_radix introsort 1000000 42
bench/bench sweep introsort 2000000 10
bench/bench run counting 5000000The bench verifies correctness after every sort and exits immediately on a bug. Random values are bounded so distribution sorts stay within reasonable memory.
lsd_radixandmsd_radixhandle negatives but notINT_MINpostmanaccepts non-negative integers onlybogois capped at n=10 in bench