# quick sort

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

# simple version using lomuto partition
function swap(A,i,j,    t) {
    t = A[i]; A[i] = A[j]; A[j] = t }

function qsort(A,lo,hi,    i,last) {
    if (lo >= hi)
        return
    swap(A, lo, lo + int((hi-lo+1) * rand()))
    last = lo
    for (i=lo+1; i<=hi; i++)
        if (A[i] < A[lo])
           swap(A, ++last, i)
    swap(A, lo, last)
    qsort(A, lo, last-1)
    qsort(A, last+1, hi) }

function sort(A,n) { qsort(A, 1, n) }

# move swaps inline and eliminate recursion
function sort(A,n,    lo,hi,i,j,t,s,p) {
    lo = 1; hi = n; p = 2
    do {
        if (hi > lo) {
            j = lo + int((hi - lo + 1) * rand())
            t = A[lo]; A[lo] = A[j]; A[j] = t
            j = lo
            for (i=lo+1; i<=hi; i++)
                if (A[i] < A[lo]) {
                    j++; t = A[j]; A[j] = A[i]; A[i] = t }
            t = A[lo]; A[lo] = A[j]; A[j] = t
            if ((j - lo) < (hi - j)) {
                s[p] = lo; s[p+1] = j - 1; lo = j + 1 }
            else { s[p] = j + 1; s[p+1] = hi; hi = j - 1 }
            p += 2 }
        else { p -= 2; lo = s[p]; hi = s[p+1] }
    } while (p > 0) }

# insert sort small sub-arrays
function sort(A,n,    lo,hi,i,j,t,s,p) {
    lo = 1; hi = n; p = 2
    do {
        if (hi - lo > 10) {
            j = lo + int((hi - lo + 1) * rand())
            t = A[lo]; A[lo] = A[j]; A[j] = t
            j = lo
            for (i=lo+1; i<=hi; i++)
                if (A[i] < A[lo]) {
                    j++; t = A[j]; A[j] = A[i]; A[i] = t }
            t = A[lo]; A[lo] = A[j]; A[j] = t
            if ((j - lo) < (hi - j)) {
                s[p] = lo; s[p+1] = j - 1; lo = j + 1 }
            else { s[p] = j + 1; s[p+1] = hi; hi = j - 1 }
            p += 2 }
        else { p -= 2; lo = s[p]; hi = s[p+1] }
    } while (p > 0)
    for (i=2; i<=n; i++) {
        t = A[i]
        for (j=i; j>1 && A[j-1] > t; j--)
            A[j] = A[j-1]
        A[j] = t } }

# approaching-pointers partition
function sort(A,n,    lo,hi,i,j,t,v,s,p) {
    lo = 1; hi = n; p = 2
    do {
        if (hi - lo > 10) {
            i = lo + int((hi - lo + 1) * rand())
            t = A[lo]; A[lo] = A[i]; A[i] = t
            j = lo + int((hi - lo + 1) * rand())
            t = A[hi]; A[hi] = A[j]; A[j] = t
            if (A[hi] < A[lo]) {
                t = A[lo]; A[lo] = A[hi]; A[hi] = t }
            v = A[hi]; i = lo; j = hi
            do {
                do { i++ } while (A[i] < v)
                do { j-- } while (v < A[j])
                t = A[i]; A[i] = A[j]; A[j] = t
            } while (i < j)
            t = A[i]; A[i] = A[hi]; A[hi] = t
            if ((i - lo) > (hi - i)) {
                s[p] = lo; s[p+1] = i - 1; lo = i + 1 }
            else { s[p] = i + 1; s[p+1] = hi; hi = i - 1 }
            p += 2 }
        else { p -= 2; lo = s[p]; hi = s[p+1] }
    } while (p > 0)
    for (i=2; i<=n; i++) {
        t = A[i]
        for (j=i; j>1 && A[j-1] > t; j--)
            A[j] = A[j-1]
        A[j] = t } }