Distribution Counting
Key {0,1,.....,M-1}
M=8
i->
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
a[i]->
3
1
1
0
3
7
5
5
2
4
2
1
0
2
6
4
count[i]
0
1
2
3
4
5
6
7
2
3
3
2
2
2
1
1
count[i]
0
1
2
3
4
5
6
7
2
5
8
10
12
14
15
16
b[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0
0
1
1
1
2
2
2
3
3
4
4
5
5
6
7
for i :=
N downto 1
do{
b[count[a[i]]] := a[i];
count[a[i]] := count[a[i]]-1;
}
T = 2N
Stable
Back to Sorting