Radix Sort (LSD)

Sort by the least-significant digit using a stable bucket pass, then by the next digit, and so on up to the most significant. No comparisons happen — values move based entirely on their own representation.

Large arrays of fixed-width integers, strings of known length, IP addresses, or anything with a small digit alphabet. Runs in O(nk) where k is the number of digits, which is effectively linear for realistic key sizes.

Keys are floats, variable-length strings without a tight bound, or comparison is cheap and n is small — the k factor plus bucket overhead wipes out the win.