Binary search finds any value in a billion sorted elements in at most 30 looks, and every one of those looks leans on the same promise: the data is already in order. Real data almost never is. So before the fast search, before merging two datasets, before spotting duplicates in one pass, something has to put the elements in order first. A sorting algorithm is that something, a procedure that takes elements in any order and rearranges them into a defined one, usually smallest to largest.

And the sorts you learn in class aren't the ones your language actually runs. Python, Java, and JavaScript all ship hybrids built from classroom pieces, and C++ ships a quicksort that knows when it's losing and swaps strategies mid-sort. This page builds those pieces from scratch: insertion sort, the O(n²) baseline, then merge sort and quicksort, the two recursive workhorses that reach O(n log n) by giving up different things, and finally the hybrids themselves.

Sorting is really a whole family of algorithms, and each member makes a different trade between speed, memory, and order preservation. Every card below jumps to the section that covers that algorithm:

Before building a single sort, you need the two words every comparison between sorts turns on: stable and in place. They sound like the same kind of virtue, and they're completely independent. Stable means equal elements keep their original relative order. Sort a spreadsheet of orders by date, then sort it again by customer with a stable sort, and each customer's orders stay in date order, since the second sort never undoes the first. In place means the sort works inside the input array with no more than O(log n) of bookkeeping, no second copy of the data. Merge sort is stable but not in place, quicksort is in place but not stable, and little insertion sort is both. Each algorithm below keeps one or both of these properties, and which one it keeps is usually why it gets picked.

You might think some undiscovered comparison sort is out there waiting to beat O(n log n) everywhere. There's a clean argument that none ever will. An array of n distinct elements can arrive in n! different orders, and a correct sort has to treat each order differently. Every comparison answers one yes or no question, which at best cuts the remaining possibilities in half, so distinguishing all 8! = 40,320 orderings of 8 elements takes at least 16 comparisons in the worst case, and in general at least log2(n!) of them, which grows as n log n. Any algorithm claiming better would be identifying one ordering out of n! without asking enough questions.

The escape hatch hides in the fine print: the bound only constrains sorts that gather information by comparing elements. Counting sort, further down this page, reads keys directly and beats the limit whenever keys are small integers.

Now here's the whole field side by side. The rest of the page walks each row, and the asterisk marks an average case:

Hand someone a messy pile of numbered cards and most people invent insertion sort on the spot: pick up the next card, slide it left past every bigger card, and drop it where it fits. The array version works the same way. The left side of the array becomes a sorted region, and each new element walks left through it until it finds its slot.

Watch it sort [5, 2, 4, 1]. The 2 walks past the 5 to give [2, 5, 4, 1], the 4 stops in front of the 5 for [2, 4, 5, 1], and the 1 walks past all three to finish [1, 2, 4, 5]. Five shifts in total, which sounds cheap. But the card analogy hides where the cost lives: cards slide aside for free, while an array has to copy every larger element one slot to the right to open the gap. Reverse-sorted input forces every element to walk the full distance, and at 1,000 elements that's 499,500 shifts. That triangle of work is what O(n²) is naming.

Now predict the opposite extreme before reading the code: how many shifts does insertion sort spend on input that's already sorted? The answer is zero: every element glances at its left neighbor once, sees nothing bigger, and stays put, so the whole pass costs O(n). Hold onto that fact, because it's the reason this slow sort survives inside every fast one.

Two more quadratic sorts share the classroom with insertion sort, and both lose to it in practice. Selection sort scans the whole unsorted region for the minimum, swaps it into place, and repeats. That sounds thrifty, but the scan ignores any order the data already has, so it costs the full O(n²) even on sorted input, and the long-range swap can fling an element past its equals, so the standard version isn't stable either.

Bubble sort compares neighbors and swaps every out-of-order pair, pass after pass, until a full pass finds nothing to do. The largest value "bubbles" to the end each round. Quick check: sorting the reversed [4, 3, 2, 1], how many swaps does it make in total? Every pair starts out of order, so all 3 + 2 + 1 = 6 of them, the same triangle of work insertion sort does in shifts. It's the sort everyone learns and nobody ships.

Insertion sort collapses at scale because elements travel one slot at a time. Merge sort never moves an element one slot at a time, and the whole algorithm is really just two observations stacked: an array with one element is already sorted, and two sorted halves can be merged into one sorted array in a single pass.

Take [38, 27, 43, 3, 9, 82, 10]. Split it into [38, 27, 43, 3] and [9, 82, 10], split those again, and keep going until every piece holds a single element. Then the merging starts and the pieces build back up: the left side becomes [3, 27, 38, 43] and the right becomes [9, 10, 82]. One merge remains, and each of its steps compares the front of one half against the front of the other and takes the smaller. Predict before reading on: which half supplies the first three elements of the final answer?

The left half gives up the 3, then the right half gives up both the 9 and the 10 before the left's 27 gets a turn. The comparing continues until the left half empties at [3, 9, 10, 27, 38, 43], and the leftover 82 is copied straight across. That copy step matters more than it looks: when one half runs out, the rest of the other half still has to come over, and forgetting it is the classic merge sort bug, because elements silently vanish from the output.

Now count the cost. Splitting produces about log n levels (the 7 elements above split 3 levels deep), and every level touches all n elements during its merges, so the total is O(n log n) on every input, sorted, reversed, or shuffled. The price is memory: a merge needs somewhere to lay elements down, so merge sort carries O(n) of scratch space. There's a quiet bonus in the tie-break, too. When both fronts are equal, the code takes from the left half, so equal elements never jump past each other: merge sort is stable.

Merge sort buys its guarantee with O(n) of extra memory. Quicksort keeps the divide-and-conquer shape but does all of its work inside the array, and its engine is the partition: pick one element, call it the pivot, and ask every other element a single question, is it smaller than the pivot or bigger?

Run that on [7, 2, 1, 6, 8, 5, 3, 4] with the last element, the 4, as the pivot. A boundary starts off the left edge and marks where the small side ends. The scan walks the array and swaps every element that's at most 4 behind the boundary: first the 2, then the 1, then the 3. When the scan ends, the pivot swaps into the slot just past the boundary, and the array reads [2, 1, 3, 4, 8, 5, 7, 6]. Look at what one pass bought. The 4 now sits at index 3, which is its final sorted position, everything to its left is smaller, and everything to its right is bigger. The 4 never moves again. Quicksort recurses on [2, 1, 3] and [8, 5, 7, 6] separately, and every partition plants one more element in its final home.

This one-scan version is called Lomuto partitioning, and it has one sharp edge worth respecting: the recursive calls must leave the pivot's index out. The pivot is the one element guaranteed to be placed, and excluding it is what makes every call strictly smaller than the last.

You might think an already sorted array is the easy case, since the work looks finished. Hand [1, 2, 3, 4, 5, 6, 7, 8] to this exact code and the opposite happens: the pivot 8 is the maximum, so the partition piles all 7 remaining elements on one side and nothing on the other. The next call inherits 7 elements and peels off one more, and the comparisons stack up as 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 for 8 elements. Sorted input is naive quicksort's O(n²) worst case, and at a million already sorted elements that's roughly 500 billion comparisons for zero useful work. The standard fixes are choosing the pivot at random or taking the median of the first, middle, and last elements, which is why quicksort's time is always quoted as O(n log n) average. What it gives up for running in place is stability: partition swaps fling equal elements across the whole array with no regard for who came first.

Quicksort rises or falls on the partition pass, so here it is broken into its five jobs:

Heapsort is the workhorse nobody picks first and everybody keeps around. It treats the array itself as a max heap, a tree packed into the array where every parent beats its children. Building the heap costs O(n), and then the sort is one move repeated: swap the root, which is the largest remaining value, into the last unsorted slot, shrink the heap by one, and sift the new root down until the heap property holds again. Each sift costs O(log n), so the whole sort is a guaranteed O(n log n), in place, with no input able to push it quadratic.

Watch it on [5, 9, 7]. Heapified, the array becomes [9, 5, 7]. Swap the 9 into the last slot for [7, 5, 9], where the 9 is now finished, then swap the new root 7 into the second-to-last slot, and [5, 7, 9] is sorted without a byte of extra memory. So why isn't heapsort the default everywhere? The answer is memory access: a sift jumps from index i to 2i + 1 and onward, bouncing across the array, while quicksort's partition streams through neighbors. Caches reward the streamer, so quicksort wins the races in practice, and heapsort earns its keep as the guarantee other sorts fall back on.

Every sort above learns by comparing, so the O(n log n) speed limit applies to all of them. Counting sort steps around the limit by never comparing anything. When keys are small integers, like exam scores from 0 to 100, it builds a 101 slot tally, walks the data once adding 1 to tally[score] for each element, and then reads the sorted result straight off the tally: write score 0 exactly tally[0] times, score 1 exactly tally[1] times, and so on. That's O(n + k) for n elements and k possible keys, so a million scores sort in about a million steps.

The catch is the k. A tally over all 32-bit integers would need about 4 billion slots, so the trick only fits when the key range is small. Radix sort stretches it: sort by the last digit with a stable counting pass, then by the next digit, and so on, so numbers up to 10 digits long sort in 10 passes. Both stay specialist tools, integer-like keys only, with O(k) extra memory as the rent.

Timsort starts from one observation about real data: it's almost never random. Log files, database rows, and half-edited lists all arrive with stretches already in order. So instead of splitting blindly down the middle like merge sort, Timsort walks the array hunting for runs, stretches that already ascend (or descend, which it reverses in place). Each run becomes a merge unit, runs shorter than a minimum length (32 to 64 elements) get extended with insertion sort, the specialist for small nearly-sorted pieces, and then the runs merge pairwise with the same stable, left-takes-ties merge from merge sort.

Two refinements make it quick in practice. The merge schedule is chosen carefully, since Python 3.11 by a policy called powersort, so runs of similar size meet each other instead of a giant run swallowing a tiny one over and over. And when one run keeps winning a merge, Timsort shifts into galloping mode, leaping ahead with a binary search instead of comparing one element at a time. That design pays off at both extremes: on data that's already sorted, the run hunter finds a single run and the whole sort finishes in O(n), while on random data it's a normal stable O(n log n) merge sort. It's never worse than merge sort and dramatically better on lived-in data, which is why Python runs it for list.sort(), why V8 adopted it for JavaScript arrays, and why Java trusts it with objects.

Introsort answers quicksort's one open weakness by standing guard over it. It begins as an ordinary quicksort, fast partitions and friendly cache behavior, but it counts its own recursion depth as it goes. A healthy quicksort on n elements bottoms out in about log2(n) levels, so when the depth passes roughly 2 log2(n), the signature of a worst case unfolding, introsort hands the misbehaving range to heapsort mid-sort. Heapsort is slower per element, but its O(n log n) ceiling is unconditional, so the hybrid inherits the guarantee while keeping quicksort's speed on inputs that behave, which is nearly all of them.

There's a third gear at the bottom: ranges below about 16 elements skip the partitioning machinery entirely and run insertion sort, which wins on tiny inputs. David Musser described the design in 1997, and it has been C++'s std::sort ever since: quicksort's speed, heapsort's guarantee, insertion sort's small-input efficiency, and the worst case of none of them.

Between them, the two hybrids above cover most of the ecosystem: Timsort behind Python and JavaScript, introsort behind C++. Java is the one worth a closer look, because it ships two different sorts, and the reason teaches the stability lesson all by itself. Sorting primitives like int[] gets a dual-pivot quicksort, a variant by Vladimir Yaroslavskiy that partitions around two pivots into three regions per pass. Why is an unstable sort acceptable there? The answer is that two equal ints are indistinguishable: there's no original order between them worth preserving, so stability stops being observable. The moment elements carry extra fields someone might have presorted, Java switches to Timsort, where stability is guaranteed.

A few footnotes complete the map. JavaScript's stability is written into the language itself: since ES2019 the spec requires Array.prototype.sort to be stable. And C++ keeps the unstable introsort as std::sort while selling stability separately as std::stable_sort, which pays merge sort's memory bill. So the answer to which sort is best is the one the libraries settled on years ago: all of them, stitched together so each one covers another's weak spot.

Sorting shows up in interviews two ways: as a tool you reach for, and as internals you get quizzed on. These habits cover both:

First, a two-question check on this page. Why is already sorted input the worst case for a last-element-pivot quicksort, and which property does each workhorse trade away, merge sort on one side and quicksort on the other? If neither one makes you hesitate, the mechanics stuck. Interview problems rarely ask you to implement a sort, though. They reward the sort-first instinct: when a problem involves overlaps, distances, rankings, or duplicates, sorting usually turns a global mess into a local one where the answer sits between neighbors.