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

function merge(A,left,middle,right,    B,i,j,k) {
    i = left; j = middle + 1
    while (i <= middle && j <= right)
        if (A[i] <= A[j]) B[++k] = A[i++]
        else B[++k] = A[j++]
    while (i <= middle)
        B[++k] = A[i++]
    while (j <= right)
        B[++k] = A[j++]
    for (k = left; k <= right; k++) {
        A[k] = B[k]; delete B[k] } }

function mergesort(A,left,right,    middle) {
    if (left < right) {
        middle = int((left + right) / 2)
        mergesort(A, left, middle)
        mergesort(A, middle + 1, right)
        merge(A, left, middle, right) } }

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

function sort(A,n,    l1,l2,u1,u2,k,g,B) {
    for (g = 1; g < n; g *= 2) {
        k = 0
        for (l1 = 1; l1 + g <= n; l1 = u2 + 1) {
            l2 = l1 + g; u1 = l2 - 1
            u2 = l2 + g - 1; if (u2 > n) u2 = n
            while (l1 <= u1 && l2 <= u2)
                if (A[l1] <= A[l2])
                    B[++k] = A[l1++]
                else B[++k] = A[l2++]
            while (l1 <= u1)
                B[++k] = A[l1++]
            while (l2 <= u2)
                B[++k] = A[l2++] }
        while (k < n)
            B[++k] = A[l1++]
        for (k = 1; k <= n; k++)
            A[k] = B[k] } }