Merge sort in AWK

mergesort.awk

function mergesort(a, len,    mid, rlen, i, left, right, ia, il, ir) {
  if (len < 2) return;
  mid = int(len / 2);
  rlen = len-mid;

  for (i=0; i<mid; i++) {left[i] = a[i];}
  for (i=0; i<rlen; i++) {right[i] = a[i+mid];}

  mergesort(left, mid)
  mergesort(right, rlen)

  ia = 0;
  il = 0;
  ir = 0;
  while (il < mid && ir < rlen) a[ia++] = (left[il] < right[ir]) ? left[il++] : right[ir++];
  while (il < mid) a[ia++] = left[il++];
  while (ir < rlen) a[ia++] = right[ir++];
}