# two linear sorts
BEGIN {
for (i=0; i<=20; i++)
tester(i)
tester(1000) }
function tester(i) {
genid(x,i); sort(x,i); check(x,i); clear(x)
gensort(x,i); sort(x,i); check(x,i); clear(x)
genrev(x,i); sort(x,i); check(x,i); clear(x)
genrand(x,i); sort(x,i); check(x,i); clear(x) }
function genid(x,n, i) {
for (i=1; i<=n; i++)
x[i] = 1 }
function gensort(x,n, i) {
for (i=1; i<=n; i++)
x[i] = i }
function genrev(x,n, i) {
for (i=1; i<=n; i++)
x[i] = n + 1 - i }
function genrand(x,n, i) {
for (i=1; i<=n; i++)
x[i] = int(n * rand()) }
function check(x,n, i) {
for (i=1; i<n; i++)
if (x[i+1]+0 < x[i]+0) {
printf "error in sort"
exit } }
function clear(x, i) {
for (i in x)
delete x[i] }
# count sort
function sort(A,n, i,s,t) {
for (i = 0; i <= n; i++) ++s[A[i]]
for (i = 1; i <= n; i++) s[i] += s[i-1]
for (i = n; i >= 0; i--) t[s[A[i]]--] = A[i]
for (i = 0; i <= n; i++) A[i] = t[i] }
# radix sort
function digit(x,k) {
while (k-- > 0)
x = int(x / 10)
return x % 10 }
function sort(A,n, b,m,p,i,s,t) {
for (m = 1; m <= n; m *= 10) b++
for (p = 0; p < b; p++) {
for (i = 0; i < 10; i++)
s[i] = 0
for (i = 1; i <= n; i++)
s[digit(A[i], p)]++
for (i = 1; i < 10; i++)
s[i] += s[i-1]
for (i = n; i >= 1; i--) {
t[s[digit(A[i], p)]] = A[i]
s[digit(A[i], p)]-- }
for (i = 1; i <= n; i++)
A[i] = t[i] } }