A sort is stable if the order of equivalent items is preserved. In Java, sorting on objects uses merge sort, a stable sort, and sorting on primitives uses quick sort, a slightly faster unstable (with shuffling) sort.
Insertion sort is stable, quick sort is not stable (except for a few partitioning schemes like 3S)
Sorts which take advantage of the alphabet an array is constructed from.
For an alphabet of size $R$, count the frequency of each key of the alphabet, then insert each element in the array at the correct location in a sorted array.
<aside> 💡
$\Theta(N + R)$ Time Complexity. The time needed to count the frequencies is $\Theta (R)$ and the time needed to insert elements from the original array is $\Theta(N)$.
</aside>
<aside> 💡
$\Theta(N + R)$ Space Complexity. Since we need $N$ to store the sorted array and $2R$ to store the starting point and frequency arrays.
</aside>
Note. Every time an element of a key $c$ is inserted, the starting position corresponding to $c$ is incremented. In this case, $R=4$.
Since the relative order of elements with matching keys is preserved, counting sort is stable.
Pair of sorts which sort digits of sequence literals (integers, strings, etc) place by place.
In the context of integer-valued arrays, it is typical to convert each element to a base (radix) $256$ number. This reduces the worst case runtime of radix sorts (decrease the number of possible digits $W$ to $4$) to $\Theta(4N+1024)$, which is an empirically optimal bound.
Counting sort, or sort with any other stable sort, by each digit starting at the right most (least significant), moving to the left.