Articles, deep dives, and notes from the engineering community.
An advanced external sorting algorithm: distributes runs evenly across a pool of input channels, executing multi-way merges into output channels, dramatically reducing the number of external storage sweep passes.
By Md. Harun-Or-Roshid
An optimized external sorting algorithm: distributes sorted runs across tape drives using Fibonacci sequence ratios to continuously merge segments without ever rewinding the tapes.
The foundational external sorting algorithm: handles datasets too massive to fit in system RAM by generating sorted segments (runs) and merging them back and forth between disk drives.
A parallel ranking algorithm: determines the final sorted position of each element by counting how many elements are smaller than it, sorting values directly with zero dependency between elements.
A parallel network routing sort: partitions elements across processors linked as a multi-dimensional hypercube, sorting data locally before routing and splitting elements along hypercube dimensions.
A non-comparison parallel sorting algorithm: counts digit frequencies concurrently across local thread processors, computing prefix sums to place items stably in parallel memory offsets.
A concurrent divide-and-conquer algorithm: partitions the array around pivot elements, spawning child threads to sort sub-partitions in parallel branches of the execution tree.
A concurrent divide-and-conquer algorithm: breaks the input down recursively, sorts sub-partitions concurrently on separate threads, and merges sorted fragments in parallel stages.
A parallel divide-and-conquer distribution sort: selects a small sample of elements to extract multiple splitters, partitioning the array into many buckets that can be sorted concurrently.
An optimal parallel sorting network: recursively sorts halves, then performs a structured series of odd-indexed and even-indexed comparison-merges to complete the sort in \(O(\log² n)\) parallel steps.
A parallel comparison network sort: recursively builds bitonic sequences (first increasing, then decreasing) before merging them in parallel steps, optimized for GPU and hardware layouts.
A mathematical sorting puzzle: sorts the array using only one allowed operation—reversing the prefix of the sequence (representing flipping a stack of pancakes with a spatula).