Sorting

A bubble sort pass swaps out-of-order adjacent pairs, carrying the largest remaining value to the end. A selection sort pass scans the unsorted region for its minimum and places it with one swap.

Insertion sort's work is proportional to how far elements must move. Each element shifts past only the larger elements before it, so nearly-ordered input costs a few shifts per element; reversed input forces every element past every predecessor.

Without the flag the outer loop always runs n-1 passes, so even an already-ordered list costs n(n-1)/2 comparisons. Tracking whether a pass swapped anything lets the algorithm stop after one clean pass, cutting the best case to n-1 comparisons.

Each pass ends with one long-range swap: the element at the region boundary is thrown to wherever the minimum was found, jumping over everything between. If an equal-keyed record sits in that gap, their relative order flips.

The invariant says the first i elements are the ones that started there, now in sorted order. It does not say they are in final positions — a later, smaller element can land among them and push the rest right.

Heapsort builds its max-heap inside the input array itself — nothing extra is allocated. The array splits into a heap prefix and a growing sorted suffix; each round swaps the root to the boundary and shrinks the heap by one.

Merge sort always halves the input until single-element runs remain, then merges back up. That gives about log2 n levels, and every level moves all n elements once, so the total is n log n whatever the input order.

Quicksort degrades to O(n^2) when every pivot splits off almost nothing — classically ordered input against a fixed first- or last-element pivot. Partitioning then peels one element per level, giving n levels of linear work instead of log n.

Heapsort swaps the root with the far end of the heap, so equal keys lose their input order. No tie-break rule inside sift-down fixes it: heap positions carry no memory of where an element started.

Stability rests on one tie-break inside the merge: when the two run heads have equal keys, take the element from the left run. A strict less-than test takes the right one instead, silently reversing equal keys.

Counting sort tallies how often each key value occurs, then turns the tallies into running totals that say where each key's block ends. A final pass copies each record into its slot — position comes from arithmetic, never comparisons.

The Omega(n log n) bound counts comparisons, and it binds only algorithms whose sole way of learning about the input is asking whether one key precedes another. Radix sort reads each key's digits directly, so it sits outside that model.

Skewed data crowds most keys into one bucket, so the per-bucket sort runs on nearly all n elements and dominates. The degraded bound is whatever that inner sort costs: quadratic with insertion sort, O(n log n) otherwise.

Each pass sorts on one digit only. Stability is what preserves the ordering earlier passes established among records that tie on the current digit. Break stability in a single pass and every lower digit's work is scrambled.

Counting sort zeroes and sweeps one counter per possible key value, so k is the key range, not the element count. A 32-bit key means billions of counters however few records you hold; it wins only while k stays near n.

The n log n floor binds only comparison sorts, which learn order solely by asking whether one key precedes another. Algorithms that read key structure directly, like radix sorts, sit outside that model and run linearly.

A stable sort preserves the input order of records whose keys compare equal. Order flight results by departure time, then sort stably by price, and flights sharing a price stay in time order. That is how multi-key ordering composes.

Insertion sort and merge sort are stable; quicksort and heapsort are not. Insertion sort, quicksort and heapsort work in place, with quicksort still spending recursion stack. Standard merge sort is the odd one out: stable, but it needs a linear-size buffer.

Model the sort as a binary tree of comparisons whose leaves are output orderings. Correctness forces n! leaves, a height-h binary tree holds at most 2^h, so h >= log2(n!), which Stirling puts at Theta(n log n).

An adaptive sort does less work when the input is already partly ordered. Insertion sort shifts only elements genuinely out of place, so its cost is proportional to n plus the number of inversions — near-linear when few items moved.

Timsort first scans for natural runs, the maximal already-ordered stretches, instead of splitting blindly. Concatenated sorted exports are a handful of very long runs, so only a few merges are needed and the total cost approaches O(n).

Heapsort is the only classic sort that is both O(n log n) in the worst case and in-place, so the guarantee costs no allocation. Merge sort would need O(n) scratch memory, which a sort that must never allocate mid-run cannot promise.

Below a cutoff of roughly 16 to 32 elements, insertion sort's tiny per-element overhead beats partitioning and recursion setup. Big-O describes growth, not small-input cost, and insertion sort has the cheapest inner loop of the elementary sorts.

Dual-pivot quicksort's comparison count is close to single-pivot's, and it performs more element moves, not fewer. Its measured advantage comes from splitting into three parts per pass, so the data is scanned end to end fewer times.

Min-run is a floor on run length, typically 32 to 64, computed from the input size so the run count lands at or just under a power of two. Runs shorter than it are grown in place by binary insertion sort, keeping merges balanced.

Quicksort is fast on average but not universally best: it is unstable and degrades toward O(n^2) with naive pivots. The defensible answer is the standard library sort, chosen after asking about size, existing order, stability needs, key type and memory.

External merge sort is needed because 500 GB will not fit in 4 GB, and an ordinary sort assumes free random access. It instead sorts memory-sized chunks into runs on disk, then merges them sequentially.

Quickselect partitions the data like quicksort, but then recurses into only the one side that can contain position k and throws the other away. That shrinking work sums to expected linear time, while sorting must order every element at O(n log n).

The linear bound is an expectation over pivot quality, not a guarantee. When pivots keep landing near an end of the range, each round strips off only a few elements, so the shrinking series becomes n + (n-1) + (n-2) + ... and the total reaches O(n^2).

Nearly sorted input rewards adaptive algorithms and punishes naive quicksort. Insertion sort and run-detecting merge hybrids approach O(n) on such data, while a quicksort choosing the first or last element as pivot partitions maximally unbadly and degrades toward O(n^2).