# 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] } }