1. Straight Radix sort ( R -> L )
  2. 124 , 324 , 223 , 321 , 123 , 131

    321 , 131 , 223 , 123 , 124 , 324

    321 , 223 , 123 , 124 , 324 , 131

    123 , 124 , 131 , 223 , 321 , 324

    íCEach pass ensures stable

    uses distribution counting

    íCExample :

    M = 1

    A 00001

    R 10010

    T 10100

    X 11000

    P 10000

    A 00001

    S 10011

    T 10100

    X 11000

    P 10000

    A 00001

    A 00001

    O 01111

    N 01110

    P 10000

    A 00001

    A 00001

    E 00101

    R 10010

    X 11000

    L 01100

    I 01001

    R 10010

    E 00101

    T 10100

    P 10000

    A 00001

    A 00001

    S 10011

    G 00111

    I 01001

    L 01100

    I 01001

    R 10010

    T 10100

    I 01001

    N 01110

    A 00001

    E 00101

    S 10011

    E 00101

    L 01100

    G 00111

    S 10011

    A 00001

    T 10100

    E 00101

    M 01101

    E 00101

    O 01111

    M 01101

    L 01100

    G 00111

    N 01110

    X 11000

    I 01001

    E 00101

    E 00101

    X 11000

    O 01111

    A 00001

    G 00111

    R 10010

    M 01101

    I 01001

    P 10000

    M 01101

    E 00101

    N 01110

    E 00101

    I 01001

    R 10010

    P 10000

    A 00001

    S 10011

    N 01110

    M 01101

    S 10011

    L 01100

    M 01101

    O 01111

    O 01111

    N 01110

    T 10100

    E 00101

    E 00101

    G 00111

    G 00111

    O 01111

    X 11000

  3. Linear sort

(1) 4 passes stright radix sort ( m = b / 4 ) => Linear

(2) passes on leading bits (almost sorted now ) + insertion sort