124 , 324 , 223 , 321 , 123 , 131
321 , 131 , 223 , 123 , 124 , 324
321 , 223 , 123 , 124 , 324 , 131
123 , 124 , 131 , 223 , 321 , 324
¡C
Each pass ensures stableuses distribution counting
¡C
Example :M = 1
A 00001 |
R 1001 0 |
T 101 00 |
X 11 000 |
P 1 0000 |
A 00001 |
S 10011 |
T 1010 0 |
X 110 00 |
P 10 000 |
A 00001 | A 00001 |
O 01111 |
N 0111 0 |
P 100 00 |
A 00001 | A 00001 |
E 00101 |
R 10010 |
X 1100 0 |
L 011 00 |
I 01 001 |
R 1 0010 |
E 00101 |
T 10100 |
P 1000 0 |
A 00001 | A 00001 |
S 1 0011 |
G 00111 |
I 01001 |
L 0110 0 |
I 010 01 |
R 10 010 |
T 1 0100 |
I 01001 |
N 01110 |
A 00001 |
E 001 01 |
S 10 011 |
E 0 0101 |
L 01100 |
G 00111 |
S 1001 1 |
A 00001 |
T 10 100 |
E 0 0101 |
M 01101 |
E 00101 |
O 0111 1 |
M 011 01 |
L 01 100 |
G 0 0111 |
N 01110 |
X 11000 |
I 0100 1 |
E 001 01 |
E 00 101 |
X 1 1000 |
O 01111 |
A 00001 |
G 0011 1 |
R 100 10 |
M 01 101 |
I 0 1001 |
P 10000 |
M 01101 |
E 0010 1 |
N 011 10 |
E 00 101 |
I 0 1001 |
R 10010 |
P 10000 |
A 00001 |
S 100 11 |
N 01 110 |
M 0 1101 |
S 10011 |
L 01100 |
M 0110 1 |
O 011 11 |
O 01 111 |
N 0 1110 |
T 10100 |
E 00101 |
E 0010 1 |
G 001 11 |
G 00 111 |
O 0 1111 |
X 11000 |
(1) 4 passes stright radix sort ( m = b / 4 ) => Linear
(2) passes on leading bits (almost sorted now ) + insertion sort