Sorting algorithms¶
Sorting arranges records according to a key or comparator. In production, use the language, database, or storage engine implementation unless the problem has unusual constraints. Implementing a sort is valuable for learning invariants, not for replacing a mature library.
For the guided stable-sort exercise, use Module 3.
Define the contract¶
State:
- sort key and ascending or descending order;
- treatment of missing values and NaN;
- whether equal-key records must retain input order;
- whether input may be mutated;
- memory and worst-case requirements;
- whether all data fits in memory.
A comparator must define a consistent ordering. Violating transitivity or changing the key during sorting makes behavior unreliable.
Stability¶
A sort is stable when equal-key records preserve their original relative order. Stability matters when:
- records were previously ordered by a secondary key;
- equality under the current key does not mean records are interchangeable;
- deterministic output is required.
Stability is an algorithm and implementation property; verify the specific library contract.
Comparison sorts¶
| Algorithm | Typical time | Worst time | Extra space | Stable | Useful property |
|---|---|---|---|---|---|
| Insertion sort | \(O(n^2)\) | \(O(n^2)\) | \(O(1)\) | yes | simple and adaptive for small/nearly sorted ranges |
| Merge sort | \(O(n\log n)\) | \(O(n\log n)\) | commonly \(O(n)\) | yes | predictable and naturally supports external merging |
| Quicksort | \(O(n\log n)\) expected | \(O(n^2)\) without safeguards | commonly \(O(\log n)\) stack expected | usually no | good locality and low overhead in suitable implementations |
| Heapsort | \(O(n\log n)\) | \(O(n\log n)\) | \(O(1)\) | no | bounded worst-case with in-place array representation |
| Hybrid library sort | implementation-dependent | documented by library | implementation-dependent | often yes | exploits runs and small partitions |
For general comparison sorting, the decision-tree model gives an \(\Omega(n\log n)\) lower bound in the worst case. This bound does not apply when an algorithm exploits additional key structure.
Insertion sort invariant¶
Before iteration \(i\), the prefix ending before \(i\) is sorted. Insert the next item into that prefix while preserving the order of equal values. It remains useful inside hybrid algorithms and for small ranges.
Merge sort invariant¶
The merge step consumes two sorted sequences and repeatedly emits the smallest remaining front item. Choosing from the left sequence first when keys are equal preserves stability.
Quicksort caution¶
Partitioning places values relative to a pivot, then sorts partitions. Pivot selection and duplicate handling determine whether adversarial input creates unbalanced recursion. Use a hardened library implementation rather than a textbook version for untrusted input.
Non-comparison sorts¶
These methods trade generality for assumptions:
| Method | Requirement | Cost shape | Main trade-off |
|---|---|---|---|
| Counting sort | integer keys in a manageable range | \(O(n+k)\) | \(O(k)\) range storage |
| Radix sort | keys decomposable into bounded digits | \(O(d(n+k))\) | multiple stable passes and representation details |
| Bucket sort | useful distribution across buckets | input-dependent | poor distribution can collapse performance |
\(k\) is the key range or digit alphabet and \(d\) is digit count. These algorithms are not simply “linear”; their additional parameters are part of the input cost.
External sorting¶
When data does not fit memory:
- read a memory-sized chunk;
- sort it and write a run;
- merge sorted runs with buffered I/O.
I/O volume, number of merge passes, temporary storage, and failure recovery dominate. A database is usually the appropriate implementation for application queries.
Selection guide¶
| Requirement | Starting choice |
|---|---|
| Ordinary in-memory records | standard library stable sort |
| Small nearly sorted range | library sort; insertion sort only in a learning/custom hybrid context |
| Guaranteed \(O(n\log n)\) and stability | merge-based implementation |
| Strict in-place and bounded comparison worst case | heapsort, if library behavior is insufficient |
| Bounded integer keys | measure counting or radix sort |
| Data larger than memory | external merge or database sort |
Correctness tests¶
Verify:
- output is ordered under the declared comparator;
- output is a permutation of input;
- stability for equal keys when promised;
- empty, single-item, sorted, reverse, and duplicate-heavy inputs;
- missing values and NaN according to contract;
- adversarial sizes and patterns for custom quicksort variants.
Compare custom results with the standard library on generated inputs. Benchmark complete sorting, including key extraction, allocation, and data movement.