Two sorting algorithms derived from Stalin Sort. Instead of discarding out-of-order elements, collect them into sorted blocks and merge everything back together.
- Sieve Sort — Multi-pass extraction of sorted subsequences + quicksort-style block merging.
- Gap Sort — Compression-aware sorting using a gap-uniformity coefficient. Detects natural runs, reassigns orphan elements to existing blocks, and merges with chain-grouped k-way merge. O(n log n).
Read the full investigation in the blog post.
Each algorithm is implemented in C, Go, and Python.