The Draftsbook Blog
Articles, deep dives, and notes from the engineering community.
External Merge Sort: Mechanism, Complexity Analysis & Interactive Visualizer
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.
By Md. Harun-Or-Roshid
Enumeration Sort: Mechanism, Complexity Analysis & Interactive Visualizer
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.
By Md. Harun-Or-Roshid
Hypercube Sort: Mechanism, Complexity Analysis & Interactive Visualizer
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.
By Md. Harun-Or-Roshid
Parallel Radix Sort: Mechanism, Complexity Analysis & Interactive Visualizer
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.
By Md. Harun-Or-Roshid
Parallel Quick Sort: Mechanism, Complexity Analysis & Interactive Visualizer
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.
By Md. Harun-Or-Roshid
Parallel Merge Sort: Mechanism, Complexity Analysis & Interactive Visualizer
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.
By Md. Harun-Or-Roshid
Sample Sort: Mechanism, Complexity Analysis & Interactive Visualizer
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.
By Md. Harun-Or-Roshid
Odd-Even Merge Sort: Mechanism, Complexity Analysis & Interactive Visualizer
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.
By Md. Harun-Or-Roshid
Bitonic Sort: Mechanism, Complexity Analysis & Interactive Visualizer
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.
By Md. Harun-Or-Roshid
Pancake Sort: Mechanism, Complexity Analysis & Interactive Visualizer
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).
By Md. Harun-Or-Roshid
Cycle Sort: Mechanism, Complexity Analysis & Interactive Visualizer
An unstable, in-place comparison sort that is theoretically optimal in terms of the total number of array writes: places every element in its final sorted slot by decomposing the array permutation into cycles.
By Md. Harun-Or-Roshid
Bead Sort (Gravity Sort): Mechanism, Complexity Analysis & Interactive Visualizer
A natural sorting algorithm: represents numbers as rows of sliding beads on vertical wires, letting gravity pull the beads down to sort the items instantly in analog hardware.
By Md. Harun-Or-Roshid