Loading...
Not all sorting algorithms are created equal. Master the fundamental properties that help you choose the right tool for any data set.
A sorting algorithm is stable if it preserves the relative order of records with equal keys. This is critical when you sort by multiple criteria (e.g., sorting by Grade, then by Name).
Uses $O(1)$ extra space. It swaps elements within the original array without needing a large temporary copy.
Requires $O(N)$ extra space, usually to hold temporary merged results or buckets.
Decides order by asking "Is A < B?"
Lower Bound Proof:
Ω(n log n)
You need at least $log(n!)$ comparisons to distinguish all possible permutations.
Uses keys directly (counting, digits)
Performance Potential:
O(n + k)
Can beat the lower bound by assuming keys are integers in a finite range.
Algorithms like Insertion Sort and TimSort are adaptive—they run faster if the input is already partially sorted (best case $O(n)$). This makes them excellent for real-world data which is rarely purely random.