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

performance analysis

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$)