Card 08/ 08
Recap: Choosing a Sorting Algorithm
The four properties that separate sorts, the comparison limit, and when a language's built-in sort is the answer.
Choosing a sort comes down to a program's constraints on memory, stability, worst case and keys, with the built-in sort as the answer when none applies. This card gathers what the topic established and where each idea was taught.
| The idea | Where |
|---|---|
| Worst time, extra space, stability and adaptivity separate the sorts, and no sort wins all four | Choosing a Sort by Memory, Stability and Worst Case |
| Five questions in order pick a linear-time sort, insertion, merge, heap or quicksort, or the built-in sort | Choosing a Sort by Memory, Stability and Worst Case |
| A comparison sort needs at least log₂(n!) comparisons, which grows as n log n; linear-time sorts do not compare | Why No Comparison Sort Can Beat n log n |
| Sorting by date and then stably by customer keeps each customer's orders in date order; a composite key does it in one sort | Sorting Orders by Date, Then by Customer |
| No spare memory and a guaranteed worst case lead to heapsort; last-item quicksort made 8,386,560 comparisons on sorted input | Sorting a Sensor Buffer With No Memory to Spare |
| Python and TypeScript sort with stable Timsort; Java uses TimSort for objects and dual-pivot quicksort for primitives | Built-In Sorts in Python, Java and TypeScript |
| TypeScript's default sort compares values as strings, so numbers need a comparator | Sorting Numbers in TypeScript Without a Comparator |
| A leaderboard, a log, a microcontroller and exam marks each have one deciding constraint | Practice: Picking the Sort for Four Programs |
- Comparison lower bound
- log₂(n!) comparisons, Ω(n log n)
- worst case, any sort that only compares
- Stable and O(n log n)
- Merge sort
- O(n) extra space
- In place and O(n log n)
- Heapsort
- not stable
- Fastest on average
- Quicksort
- O(n²) worst case, O(log n) stack
- Nearly sorted input
- Insertion sort
- O(n) on sorted input
- Built-in sorts for objects
- Stable in Python, Java and TypeScript
- Timsort family
The sorts of the earlier topics are no longer competitors but tools for different constraints, and the built-in sort covers most programs that have none. Backtracking, a later topic, begins the design strategies that reach beyond sorting.
← → move through sections and cards