Algorithms - sorting

You almost never implement a sort in production. What matters is knowing which sort your stdlib runs, when stability matters, and when sorting is the wrong move.

Defaults to know

Language	Default sort	Stable	Notes
Python list.sort / sorted	Timsort	Yes	Adaptive — fast on partially-sorted data
Java Arrays.sort (objects)	Timsort	Yes
Java Arrays.sort (primitives)	Dual-pivot quicksort	No
C++ std::sort	Introsort	No	Quicksort + heapsort fallback
C++ std::stable_sort	Mergesort variant	Yes
Rust Vec::sort	Timsort	Yes
Rust Vec::sort_unstable	Pattern-defeating quicksort	No	Faster, no stability

Reach for stable when: secondary sort key matters, you’re sorting records with equal keys whose original order encodes information.

When NOT to sort

• You only need the top k. Use a heap — O(n log k) beats O(n log n) when k ≪ n.
• You only need the median / kth. Quickselect is O(n) average.
• You’ll only do range queries. A sorted array helps only if it stays static; otherwise BTree.
• You only need “is sorted” / “is duplicate.” Linear scan or hash set, no sort.
• The data is already mostly sorted. Insertion sort is O(n) on already-sorted; Timsort exploits runs.

Algorithms worth knowing the shape of

• Mergesort. O(n log n), stable, O(n) extra memory. The textbook divide-and-conquer. External sort variant is what you use when data exceeds memory.
• Quicksort. O(n log n) average, O(n²) worst. Pivot choice is everything. Used because of cache friendliness, not asymptotic.
• Heapsort. O(n log n) worst case, O(1) extra memory, not stable. Used inside introsort as the “abort to” when quicksort goes pathological.
• Counting / radix. O(n + k) where k is range. Beats comparison sorts when k is small (e.g. byte-level radix on 32-bit ints). Niche but valuable.

External sort, briefly

When data > RAM: chunk into RAM-sized pieces, sort each in memory, write out, then k-way merge with a min-heap. This is what databases do for ORDER BY over large tables; understanding the shape helps you reason about disk I/O patterns and work_mem tuning in Postgres.