the best that all comparison-based sorting can do is $O(n\log n)$
radix sort performs better than comparison-based sorting algorithms when keys are short (small m) and arrays are large (large n)
consider each item as a tuple
e.g. represent “sydney” as (s, y, d, n, e, y) OR “372” as (3, 7, 2)
where the $i$th element of each tuple is denoted by $k_i$
radix sort assumes only a small number of possible values for $k_i$
for a list of values of length $m$, stable sort on the last element ($k_m$),
then second last $k_{m-1}$… until we reach $k_1$
since there are only a small number of possible values, we can use bucket sort (O(n)) to simply place each value into a bucket according to the $i$th element, then empty the buckets in order to maintain stability
for each i in m .. i do
empty all buckets
for each key in A do
append key to bucket[key[i]]
clear A
for each bucket in order do
for each key in bucket do
append to A
if an array has $n$ values, and each value is of length $m$, then bucket sort (O($n$)) must be run $m$ times → overall time complexity is O($mn$)