The Draftsbook Blog
Articles, deep dives, and notes from the engineering community.
ProxmapSort: Mechanism, Complexity Analysis & Interactive Visualizer
A high-performance distribution sort: maps elements directly to their proximity slots in a destination array using a mapping function, resolving slot collisions with local insertion sort.
By Md. Harun-Or-Roshid
Burstsort: Mechanism, Complexity Analysis & Interactive Visualizer
A state-of-the-art string-based sorting algorithm: dynamically builds a trie with leaf-level buckets, "bursting" buckets into sub-tries when they grow too large, followed by a fast comparison sort sweep.
By Md. Harun-Or-Roshid
Gnome Sort: Mechanism, Complexity Analysis & Interactive Visualizer
The garden gnome sort: a remarkably simple single-loop exchange sort modeled after a gnome checking adjacent flowerpots and moving backward or forward accordingly.
By Md. Harun-Or-Roshid
Odd-Even Sort: Mechanism, Complexity Analysis & Interactive Visualizer
A highly parallelizable exchange sort: alternates between swapping adjacent odd-indexed pairs and even-indexed pairs, forming the basis for hardware-based sorting networks.
By Md. Harun-Or-Roshid
Cocktail Shaker Sort: Mechanism, Complexity Analysis & Interactive Visualizer
A bidirectional bubble sort: bubbles values back and forth in alternating directions to quickly clear slow-moving small values ("turtles") and large values ("rabbits").
By Md. Harun-Or-Roshid
Comb Sort: Mechanism, Complexity Analysis & Interactive Visualizer
An ingenious improvement on Bubble Sort: compares elements at a shrinking gap size to eliminate small values trapped near the end of the array ("turtles") before finishing with a final bubble pass.
By Md. Harun-Or-Roshid
Spreadsort: Mechanism, Complexity Analysis & Interactive Visualizer
A state-of-the-art hybrid distribution sort: combines bucket partitioning based on key bits with standard comparison algorithms for small bins, outperforming Quicksort on many datasets.
By Md. Harun-Or-Roshid
Block Sort: Mechanism, Complexity Analysis & Interactive Visualizer
The holy grail of comparison sorts: an in-place, stable hybrid algorithm that achieves O(n log n) efficiency without requiring any auxiliary heap or merge memory buffers.
By Md. Harun-Or-Roshid
IntroSort: Mechanism, Complexity Analysis & Interactive Visualizer
A hybrid sorting algorithm: starts with Quick Sort for high speed, switches to Heap Sort if recursion limits are hit, and drops to Insertion Sort for tiny subarrays.
By Md. Harun-Or-Roshid
TimSort: Mechanism, Complexity Analysis & Interactive Visualizer
The modern industry-standard sorting algorithm: a high-performance hybrid of Merge Sort and Insertion Sort designed to exploit pre-existing order in real-world data.
By Md. Harun-Or-Roshid
Splay Tree Sort: Mechanism, Complexity Analysis & Interactive Visualizer
A self-adjusting search tree sort: elements are inserted into a Splay Tree, splaying recently accessed nodes to the root, followed by an in-order retrieval.
By Md. Harun-Or-Roshid
Cartesian Tree Sort: Mechanism, Complexity Analysis & Interactive Visualizer
An adaptive, heap-based algorithm: build a min-heap structured Cartesian tree in linear time, then sort by repeatedly pulling the minimum element into a priority queue.
By Md. Harun-Or-Roshid