# two sub-quadratic 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] }

function sort(A,n,    gap,i,switched,t) {
    gap = n
    do {
        if (gap > 1)
            gap = int(gap / 1.3)
        switched = 0
        for (i=1; i<=n-gap; i++)
            if (A[i+gap] < A[i]) {
                t = A[i]; A[i] = A[i+gap]; A[i+gap] = t
                switched = 1 }
    } while (switched || gap > 1) }

function sort(A,n,    gap,i,j,t) {
    while (gap < n)
        gap = 3 * gap + 1
    while (gap > 1) {
        gap = int(gap / 3)
        for (i=gap+1; i<=n; i++) {
            t = A[i]
            for (j=i; gap<j && t<A[j-gap]; j-=gap)
                A[j] = A[j-gap]
            A[j] = t } } }