Sorting and Selection

Sorting arranges elements in order. Selection finds the $k$ -th smallest (or largest) element without fully sorting.

Key algorithms:

Algorithm	Time	Space	Stable?	Notes
Quicksort	$O(n \log n)$ avg, $O(n^2)$ worst	$O(\log n)$	No	Default in most libraries (introsort variant)
Mergesort	$O(n \log n)$ always	$O(n)$	Yes	Stable, used when stability matters
Heapsort	$O(n \log n)$ always	$O(1)$	No	In-place but poor cache behavior
Radix sort	$O(nk)$	$O(n)$	Yes	For integers/fixed-width keys; $k$ = key length

Selection without full sort:

Quickselect — partitioning-based, $O(n)$ average for the $k$ -th element
np.argpartition(arr, k) — finds top- $k$ in $O(n)$ instead of $O(n \log n)$ argsort

Where this matters in ML:

Top- $k$ sampling — selecting the $k$ highest-probability tokens for generation. Quickselect makes this $O(|V|)$ instead of $O(|V| \log |V|)$
Top- $k$ retrieval — ranking candidates by similarity score
Argsort — torch.argsort() for ranking predictions, computing rank-based metrics (MRR, NDCG)
Non-maximum suppression — sorting bounding boxes by confidence in object detection
Sorting networks — differentiable sorting for end-to-end learning (SortNet, NeuralSort)
Batching by sequence length — sorting samples to minimize padding waste in NLP

Stability matters when you have a secondary sort criterion — e.g., sorting predictions by score but preserving insertion order for ties.

Linked from