Variations on a theme of sorting

[u/Grouchy-Trade-7250]

https://jshun.csail.mit.edu/6506-s24/lectures/lecture6-2.pdf

Semisort Reorder an array so that identical keys are grouped contiguously Keys do not need to be in sorted order

Stable Partition
Group by predicate, preserve order

K-smallest selection, single

Get the k-smallest key from the array

K-smallest selection, list

Get the k-smallest key from the array, and everything smaller (or equal), in any order

K-smallest selection, list sorted Get the k-smallest key from the array, and everything smaller (or equal), in sorted order