The Draftsbook Blog
Articles, deep dives, and notes from the engineering community.
Three-Way Quick Sort: Mechanism, Complexity Analysis & Interactive Visualizer
Partition into three regions — less than, equal to, and greater than the pivot — so duplicates are sorted by being touched only once.
By Md. Harun-Or-Roshid
Randomized Quick Sort: Mechanism, Complexity Analysis & Interactive Visualizer
Pick the pivot uniformly at random. The expected runtime is O(n log n) on every input — no adversary can construct a bad case.
By Md. Harun-Or-Roshid
Quick Sort: Mechanism, Complexity Analysis & Interactive Visualizer
Choose a pivot, partition the array around it, recurse on each side. Average O(n log n) with tiny constants — the default sort in many languages.
By Md. Harun-Or-Roshid
In-Place Merge Sort: Mechanism, Complexity Analysis & Interactive Visualizer
Trade time for memory: merge two sorted halves using rotations, eliminating the O(n) buffer at the cost of an extra log factor on writes.
By Md. Harun-Or-Roshid
Bottom-Up Merge Sort: Mechanism, Complexity Analysis & Interactive Visualizer
Same merges, no recursion. Walk over the array in runs of size 1, then 2, then 4, doubling each pass until the whole array is one run.
By Md. Harun-Or-Roshid
Merge Sort: Mechanism, Complexity Analysis & Interactive Visualizer
Split the array in half, sort each half recursively, then merge the two sorted halves. Guaranteed O(n log n), always stable.
By Md. Harun-Or-Roshid
Shell Sort: Mechanism, Complexity Analysis & Interactive Visualizer
Insertion Sort, but on widely-spaced sub-arrays first. The gap shrinks each pass until a final gap of 1 finishes a nearly-sorted array fast.
By Md. Harun-Or-Roshid
Binary Insertion Sort: Mechanism, Complexity Analysis & Interactive Visualizer
Insertion Sort with a smarter probe: use binary search to find where the new element belongs in O(log n), then shift.
By Md. Harun-Or-Roshid
Insertion Sort: Mechanism, Complexity Analysis & Interactive Visualizer
Take each new element and slide it left over larger neighbors until it lands in the right slot — like sorting a hand of cards.
By Md. Harun-Or-Roshid
Selection Sort: Mechanism, Complexity Analysis & Interactive Visualizer
Find the smallest element in the unsorted region, swap it to the front, and shrink the region. Minimum writes among the simple sorts.
By Md. Harun-Or-Roshid
Optimized Bubble Sort: Mechanism, Complexity Analysis & Interactive Visualizer
Bubble Sort with two small but valuable improvements: an early-exit flag and a shrinking last-swap boundary. The asymptotic class doesn't change, but real inputs run dramatically faster.
By Md. Harun-Or-Roshid
Bubble Sort: Mechanism, Complexity Analysis & Interactive Visualizer
The classic teaching algorithm: repeatedly walk the array, swap any out-of-order neighbors, and let the largest element bubble to the top of each pass.
By Md. Harun-Or-Roshid