#include <time.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct sym SYM;

struct sym {
  uint32_t val;
  } ;

static SYM sv[256];
static int nsv;
static uint32_t minv;
static uint32_t maxv;

static void gen_syms(void)
{
 int i;

 srandom(time(0));
 nsv = (random() & ((1 << (random() & 7)) - 1)) + 1;
 for (i=nsv-1;i>=0;i--) sv[i].val = random() & 0xff;
 minv = sv[0].val;
 maxv = minv;
 for (i=nsv-1;i>0;i--)
  { if (sv[i].val < minv) minv = sv[i].val;
    if (sv[i].val > maxv) maxv = sv[i].val;
  }
}

static void dump_syms(SYM *v, int n, int indent)
{
 int i;

 for (i=0;i<n;i++)
  { printf("%*s%08lx\n",indent,"",(unsigned long int)v[i].val);
  }
}

static void sort_syms(SYM *v, int n, uint32_t min, uint32_t max, int depth)
{
 int a;
 int b;
 SYM t;
 uint32_t mid;

 printf("%*ssort_syms entry: base %d n %d, min %08lx max %08lx\n",
	depth,"",(int)(v-&sv[0]),n,(unsigned long int)min,(unsigned long int)max);
 while (1)
  { if (n < 2) return;
    if (max-min < 1) return;
    mid = (min + max) / 2;
    a = 0;
    b = n - 1;
    while (1)
     { while ((a < b) && (v[a].val <= mid)) a ++;
       while ((b > a) && (v[b].val > mid)) b --;
       if (a == b) break;
       t = v[a];
       v[a] = v[b];
       v[b] = t;
     }
    if (v[b].val <= mid) b ++;
    printf("%*ssplit list\n",depth,"");
    dump_syms(v,b,depth+8);
    printf("%*s--------\n",depth,"");
    dump_syms(v+b,n-b,depth+8);
    if (max-min == 1) return;
    if (n-b < b)
     { sort_syms(v+b,n-b,mid,max,depth+2);
       n = b;
       max = mid;
     }
    else
     { sort_syms(v,b,min,mid,depth+2);
       v += b;
       n -= b;
       min = mid;
     }
    depth += 2;
    printf("%*ssort_syms tailcall: base %d n %d, min %08lx max %08lx\n",
	depth,"",(int)(v-&sv[0]),n,(unsigned long int)min,(unsigned long int)max);
  }
}

int main(void);
int main(void)
{
 gen_syms();
 printf("list size = %d\n",nsv);
 printf("Initial list\n");
 dump_syms(&sv[0],nsv,8);
 sort_syms(sv,nsv,minv,maxv,0);
 printf("Sorted list\n");
 dump_syms(&sv[0],nsv,8);
 return(0);
}