n-wayAdaptive merge sort. Merge arity scales with your data — from quadsort-style 4-way to K-way heap merge with K up to 1024.
$ make && ./bench
n=100000 ints, 5 reps
algorithm time (s)
qsort 0.006082
polysort 0.010978
_
Full specification, run-time analysis, benchmarks, and distributed extensions.
Polysort vs qsort and distributed variants on 100K random integers, 5 runs each.
All algorithms produce correctly sorted output. Library qsort is fastest at this scale — Polysort is designed to scale as n and K grow.
Four phases from raw input to fully sorted output.
Divide array into blocks of 32, sort each with insertion sort.
K = clamp(4, √n, 1024). Merge arity scales with input size.
Min-heap merge of up to K runs. Stable — tie-break by run index.
Alternate between base and auxiliary buffer. Copy back when done.
Three distributed sorting paradigms, all built on the same core primitives: run building and K-way merge.
Two-phase sort: map-side polysort per chunk, shuffle-partition by sampled split points, then K-way merge per reducer.
Range-partition unsorted input in one pass, sort each partition independently with polysort, then concatenate.
Recursive K-way merge tree: split into K sub-ranges, sort recursively, merge with single K-way pass.
Designed for scalability, stability, and seamless integration.
Merge arity K scales with input size — K ≈ √n, capped at 1024. Fewer passes as data grows.
Preserves relative order of equal elements via min-heap tie-breaking by run index.
Drop-in replacement for standard C qsort with the same function signature.
Single merge buffer plus run descriptors. Falls back to in-place sort on allocation failure.
MapReduce, Spark, and Dryad-style sorting — all built on the same core primitives.
ANSI C, modular architecture, full test coverage, and permissive license.