Radix sort basic idea:

• represent key as a tuple (k₁, k₂, ..., k_m), for example
  • represent key 372 as (3, 7, 2)
  • represent key sydney as (s, y, d, n, e, y)
• finite and normally few possible values of k_i, for example
  • numeric: 0 to 9
  • alpha-numeric: 0 to 9 , a to z
• sorting algorithm:
  • stable sort on k_m,
  • then stable sort on k_(m-1),
  • similarly continue until k₁
• time complexity:
  • stable sort like bucket/pigeonhole sort runs in time O(n)
  • radix sort runs in time O(mn) , where m is number of sub-keys (k_i in a tuple above)
  • radix sort performs better (for sufficiently large n) than the best comparison-based sorting algorithms

See radix sort example below,