When to Use Non-Comparison Sorts

Non-comparison sorts beat $O(n \log n)$ but only under specific conditions.

Use counting sort when:

• Values are integers in a small range $[0, k]$ where $k = O(n)$.
• Example: Sorting exam scores from $0$ to $100$ for $n = 1000$ students.

Use radix sort when:

• Values are integers or strings with bounded length.
• The number of digits $d$ is small compared to $\log n$.
• Example: Sorting $n$ integers up to $n^2$. Radix sort takes $O(n)$ because $d = 2$ in base $n$.

Avoid them when:

• Range is huge (counting sort needs $O(k)$ space).
• Values are floats or arbitrary objects.
• You need in-place sorting with $O(1)$ extra space.