Counting Sort

Count how many times each key value occurs, turn the counts into a prefix sum, then place each input element directly at its final index. One scan to count, one to place — no comparisons involved.

Integer keys drawn from a small known range — grading curves, histogramming, pixel intensities, bucket step inside radix sort. Linear in n + k and naturally stable.

The key range k dwarfs the array size n. You end up allocating and scanning an enormous counts array for very little actual work.