Articles, deep dives, and notes from the engineering community.
An elegant comparison-based sorting algorithm that organizes data into a binary heap to extract elements in sorted order efficiently and in-place.
By Md. Harun-Or-Roshid
Two pivots, three partitions. Vladimir Yaroslavskiy's 2009 variant became the default sort in Java 7 and runs about 10–20% faster than classical quicksort.
Partition into three regions — less than, equal to, and greater than the pivot — so duplicates are sorted by being touched only once.
Pick the pivot uniformly at random. The expected runtime is O(n log n) on every input — no adversary can construct a bad case.
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.
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.
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.
Split the array in half, sort each half recursively, then merge the two sorted halves. Guaranteed O(n log n), always stable.
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.
Insertion Sort with a smarter probe: use binary search to find where the new element belongs in O(log n), then shift.
Take each new element and slide it left over larger neighbors until it lands in the right slot — like sorting a hand of cards.
Find the smallest element in the unsorted region, swap it to the front, and shrink the region. Minimum writes among the simple sorts.