Sorting Algorithms: every key term you need (+ practice quiz)
25 flashcard terms for Data Structures & Algorithms Topic 4, written to match the course framework. Study them here, then drill them as interactive flashcards, or test yourself with the 15-question quiz — free, no account needed.
Any sort that only compares keys needs Omega(n log n) comparisons in the worst case, because a decision tree with n factorial leaves must have height at least log of n factorial.
Sorting stability
The property that equal keys keep their original relative order. It matters when sorting repeatedly on different fields, since a stable pass preserves the earlier ordering.
Insertion sort
Builds a sorted prefix by shifting each new element back into place. Quadratic in the worst case, linear on nearly sorted data, stable, in place and excellent for tiny arrays.
Selection sort
Repeatedly finds the smallest remaining element and swaps it into position. Always quadratic in comparisons but uses only n minus one swaps, which suits costly write operations.
Bubble sort
Repeatedly sweeps adjacent pairs and swaps those out of order until a pass makes no swap. Quadratic and slow in practice, kept mainly as a teaching example of an adaptive early exit.
Shell sort
Runs insertion sort on elements spaced by a decreasing gap sequence so long-distance disorder is fixed early. Its bound depends on the gap sequence and beats quadratic in practice.
Quicksort
Partitions around a pivot then sorts each side recursively. Average Theta(n log n) with small constants, worst case quadratic on bad pivots, in place but not stable.
Lomuto partition
Scans with one index, swapping elements below the pivot forward, then places the pivot in the gap. Simple to write but performs more swaps and degrades badly on many equal keys.
Hoare partition
Advances two indices from opposite ends and swaps inverted pairs until they cross. It does fewer swaps than the one-index scheme and handles repeated keys far more gracefully.
Pivot selection
The rule choosing the split point in quicksort. A fixed end element invites quadratic behaviour on sorted input, while median of three or a random draw makes that outcome unlikely.
Randomized quicksort
Picks the pivot uniformly at random so no fixed input pattern is adversarial. Expected cost is Theta(n log n) with the probability of severe imbalance falling off sharply.
Introsort
Runs quicksort but watches recursion depth, switching to heapsort past a log n threshold and to insertion sort on small ranges. It keeps quicksort speed with a guaranteed bound.
Heapsort
Builds a max heap in linear time then repeatedly swaps the root to the end and sifts down. Worst-case Theta(n log n), in place, unstable and cache-unfriendly compared with merging.
Bottom-up merging
An iterative sort that merges runs of length one, then two, then four, avoiding recursion entirely while keeping the linearithmic bound and stability of the recursive version.
Natural run detection
Scanning the input for already ordered stretches and merging those instead of fixed blocks, so partially ordered data is sorted in close to linear time.
Timsort
A hybrid stable sort that finds natural runs, extends short ones with insertion sort, and merges under stack invariants that keep run lengths balanced. Linearithmic worst case.
Counting sort
Tallies occurrences of each key in a small integer range then writes output by prefix sums. Runs in O(n plus k) time and is stable, but needs a table sized by the key range.
Radix sort
Sorts fixed-width keys digit by digit using a stable pass per digit, giving O(d times (n plus b)) time for d digits and base b, with no key comparisons at all.
Bucket sort
Distributes keys into ordered buckets by value, sorts each bucket, and concatenates. Expected linear time when keys are roughly uniform, degrading if they cluster in one bucket.
External merge sort
Sorts data larger than memory by producing sorted runs that fit in RAM then merging many runs at once, minimising disk passes rather than comparisons.
Adaptive sorting
Behaviour where existing order lowers the cost, measured by inversions or run count. Insertion sort and run-based merging are adaptive; selection sort is not.
Sorting network
A fixed sequence of compare-and-swap pairs independent of the data, so it can run in parallel or in hardware. Correctness follows from the zero one principle.
Comparator contract
The requirement that an ordering function be consistent and transitive with a total order. Violating it can make library sorts produce garbage or read outside the array.
Key-indexed distribution
Placing records directly at positions computed from key values using cumulative counts, the mechanism behind counting and radix sorting that avoids comparisons entirely.
Partial sorting
Producing only the k smallest items in order, achievable in O(n log k) with a bounded heap or in expected linear time with selection followed by a small sort.