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