/*
 * Title: Sorting Knuth
 * Date:  Sept 1, 1999
 * From:  Marc Tardif aka MrPickle
 * Email: intmktg@cam.org
 *
 * To compile: cc file.c -lm
 *
 * 2000/01/29 jh: Fixed the code to be ANSI-compatible
 */

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

#define u 0     /* minimal key value */
#define v 16    /* maximal key value, inclusive */

#define pop(a, b)       a = (--St)->i, b = St->j, S-=1
#define push(a, b)      St->i = a, (St++)->j = b, S+=1
#define swap(a, b, t)   t = a, a = b, b = t
#define set(a,b)        ((b<0)?set2(a,-b):set2(a,b))
#define set2(a,b)       ((a<0)?-b:b)

typedef struct {
	int K;		/* Key */
	int L;		/* Link */
} RECORD;

typedef struct {
	int i;		/* not significant */
	int j;		/* not significant */
} STACK;

typedef enum {
	LOW,
	HIGH
} ROUND;

void ccount(RECORD **, int);    /* Comparison counting */
void dcount(RECORD **, int);    /* Distribution counting */
void ins(RECORD **, int);       /* Straight insertion */
void shl(RECORD **, int);       /* Shell's method */
void lins(RECORD **, int);      /* List insertion */
void bubble(RECORD **, int);    /* Bubble sort */
void merge(RECORD **, int);     /* Merge exchange */
void quick(RECORD **, int);     /* Quicksort */
void radix(RECORD **, int);     /* Radix exchange sort */
void straight(RECORD **, int);  /* Straight selection sort */
void heap(RECORD **, int);      /* Heapsort */
void tmerge(RECORD **, int);    /* Two-way merge */
void ntmerge(RECORD **, int);   /* Natural two-way merge sort */
void stmerge(RECORD **, int);   /* Straight two-way merge sort */
void lmerge(RECORD **, int);    /* List merge sort */

void fill(RECORD **, int);
void printarray(RECORD **, int);
void printlist(RECORD **);
void fatal(char *);
void usage(void);

int lg(int, ROUND);

int main(int argc, char *argv[]) {
	extern int optind;
	RECORD **R;
	int i, ch, N;

	if (argc<2)
		usage();

	/* Number of records */
	N = 16;

	if (!(R = (RECORD **)malloc((N+1)*sizeof(RECORD *))))
		fatal("malloc");
	for (i=0; i<=N; i++)
		if (!(R[i] = (RECORD *)malloc(sizeof(RECORD))))
			fatal("malloc");

	fill(R, N);

	while ((ch = getopt(argc, argv, "cdielbmqrshtngw")) != EOF) {
		switch (ch) {
		case 'c':
			printf("Comparison counting:\n");
			ccount(R, N);
			break;
		case 'd':
			printf("Distribution counting:\n");
			dcount(R, N);
			break;
		case 'i':
			printf("Straight insertion:\n");
			ins(R, N);
			break;
		case 'e':
			printf("Shell's method:\n");
			shl(R, N);
			break;
		case 'l':
			printf("List insertion:\n");
			lins(R, N);
			break;
		case 'b':
			printf("Bubble sort:\n");
			bubble(R, N);
			break;
		case 'm':
			printf("Merge exchange:\n");
			merge(R, N);
			break;
		case 'q':
			printf("Quicksort:\n");
			quick(R, N);
			break;
		case 'r':
			printf("Radix exchange sort:\n");
			radix(R, N);
			break;
		case 's':
			printf("Straight selection sort:\n");
			straight(R, N);
			break;
		case 'h':
			printf("Heapsort:\n");
			heap(R, N);
			break;
		case 't':
			printf("Two-way merge:\n");
			tmerge(R, N);
			break;
		case 'n':
			printf("Natural two-way merge sort:\n");
			ntmerge(R, N);
			break;
		case 'g':
			printf("Straight two-way merge sort:\n");
			stmerge(R, N);
			break;
		case 'w':
			printf("List merge sort:\n");
			lmerge(R, N);
			break;
		default:
			usage();
			break;
		}
	}
	argc -= optind;
	argv += optind;

	if (R[0]->L)
		printlist(R);
	else
		printarray(R, N);

	return(0);
}

void ccount(RECORD **R, int N) {
		int i, j;
		int *COUNT = (int *)malloc((N+1)*sizeof(int));

C1:		for (i=1; i<=N; i+=1) COUNT[i]=0;
C2:		for (i=N; i>=2; i-=1) {
C3:			for (j=i-1; j>=1; j-=1) {
C4:				if (R[i]->K < R[j]->K) COUNT[j]+=1; else COUNT[i]+=1; } }

		for (i=1; i<=N; i++) R[i]->L=COUNT[i];
}

void dcount(RECORD **R, int N) {
		int i, j;
		int *COUNT = (int *)malloc((v-u+1)*sizeof(int));
		int *S = (int *)malloc((N+1)*sizeof(int));

D1:		for (i=u; i<=v; i+=1) COUNT[i]=0;
D2:		for (j=1; j<=N; j+=1)
D3:			COUNT[R[j]->K]+=1;
D4:		for (i=u+1; i<=v; i+=1) COUNT[i]+=COUNT[i-1];
D5:		for (j=N; j>=1; j-=1) {
D6:			i=COUNT[R[j]->K]; S[i]=R[j]->K; COUNT[R[j]->K]=i-1; }

		for (i=1; i<=N; i++) R[i]->K=S[i];
}

void ins(RECORD **R, int N) {
		int i, j, Kt;
		RECORD *Rt = (RECORD *)malloc(sizeof(RECORD));

S1:		for (j=2; j<=N; j+=1) {
S2:			i=j-1; Kt=R[j]->K; Rt=R[j];
S3:			if (Kt>=R[i]->K) goto S5;
S4:			R[i+1]=R[i]; i-=1; if (i>0) goto S3;
S5:			R[i+1]=Rt; }
}

void shl(RECORD **R, int N) {
		int i, j, h, Kt;
		RECORD *Rt = (RECORD *)malloc(sizeof(RECORD));

D1:		for (h=N/2; h>0; h/=2) {
D2:			for (j=h+1; j<=N; j+=1) {
D3:				i=j-h; Kt=R[j]->K; Rt=R[j];
D4:				if (Kt>=R[i]->K) goto D6;
D5:				R[i+h]=R[i]; i-=h; if (i>0) goto D4;
D6:				R[i+h]=Rt; } }
}

void lins(RECORD **R, int N) {
		int j, p, q, Kt;
		RECORD *Rt = (RECORD *)malloc(sizeof(RECORD));

L1:		R[0]->L=N; R[N]->L=0; for (j=N-1; j>=1; j-=1) {
L2:			p=R[0]->L; q=0; Kt=R[j]->K;
L3:			if (Kt<=R[p]->K) goto L5;
L4:			q=p; p=R[q]->L; if (p>0) goto L3;
L5:			R[q]->L=j; R[j]->L=p; }
}

void bubble(RECORD **R, int N) {
		int j, t, BOUND;
		RECORD *Rt = (RECORD *)malloc(sizeof(RECORD));

B1:		BOUND=N;
B2:		t=0; for (j=1; j<=BOUND-1; j+=1) {
B3:			if (R[j]->K>R[j+1]->K) swap(R[j],R[j+1],Rt); t=j; }
B4:		if (t!=0) { BOUND=t; goto B2; }
}

void merge(RECORD **R, int N) {
		int i, j, d, p, q, r, t;
		RECORD *Rt = (RECORD *)malloc(sizeof(RECORD));

M1:		t=lg(N, HIGH); for (j=1, p=pow(2,t-1); p>=1; p=pow(2,t-(j++))) {
M2:			q=pow(2, t-1); r=0; d=p;
M3:			for (i=0; i<N-d; i+=1) if ((i&p)==r) {
M4:				if (R[i+1]->K>R[i+d+1]->K) swap(R[i+1],R[i+d+1],Rt); }
M5:			if (q!=p) { d=q-p; q=q/2; r=p; goto M3; } }
M6:		p=p/2; if (p>0) goto M2;
}

void quick(RECORD **R, int N) {
		int i, j, l, d, p, q, r, K, S;
		int M = 7;
		RECORD *Rt = (RECORD *)malloc(sizeof(RECORD));
		STACK *St = (STACK *)malloc((lg(N, HIGH)+1)*sizeof(STACK));

Q1:		if (N<=M) goto Q9; S=0; l=1; r=N;
Q2:		i=l; j=r+1; K=R[l]->K;
Q3:		i+=1; if (R[i]->K<K) goto Q3;
Q4:		j-=1; if (K<R[j]->K) goto Q4;
Q5:		if (j<=i) { swap(R[l],R[j],Rt); goto Q7; }
Q6:		swap(R[i],R[j],Rt); goto Q3;
Q7:		if (r-j>=j-l>M) { push(j+1,r); S+=1; r=j-1; goto Q2; }
		if (j-l>r-j>M) { push(l,j-1); S+=1; l=j+1; goto Q2; }
		if (r-j>M>=j-l) { l=j+1; goto Q2; }
		if (j-l>M>=r-j) { r=j-1; goto Q2; }
Q8:		if (S) { pop(l,r); S-=1; goto Q2; }
Q9:		for (j=2; j<=N; j+=1) {
			if (R[j-1]->K > R[j]->K) {
					K=R[j]->K; Rt=R[j]; i=j-1; R[i+1]=R[i];
					while (R[i]->K>K && i>=1) i-=1;
					R[i+1]=Rt; } }
}

void radix(RECORD **R, int N) {
		int i, j, b, l, m, r, S;
		STACK *St;
		RECORD *Rt = (RECORD *)malloc(sizeof(RECORD));

		m = (sizeof(int)*8);
		St = (STACK *)malloc((m-1)*sizeof(STACK));

R1:		S=0; l=1; r=N; b=N;
R2:		if (l==r) goto R10; i=l; j=r;
R3:		if (R[i]->K & 1<<(b-1)) goto R6;
R4:		i+=1; if (i<=j) goto R3; goto R8;
R5:		if (!(R[j+1]->K & 1<<(b-1))) goto R7;
R6:		j-=1; if (i<=j) goto R5; goto R8;
R7:		swap(R[i],R[j+1],Rt); goto R4;
R8:		b-=1; if (b<0) goto R10;
		if (j<l || j==r) goto R2;
		if (j==l) { l+=1; goto R2; }
R9:		push(r,b); r=j; goto R2;
R10:	if (S) { l=r+1; pop(r,b); goto R2; }
}

void straight(RECORD **R, int N) {
		int i, j, k;
		RECORD *Rt = (RECORD *)malloc(sizeof(RECORD));

S1:		for (j=N; j>=2; j-=1) {
S2:			for (i=j, k=j-1; k>=1; k-=1) if (R[k]->K>R[i]->K) i=k;
S3:			swap(R[i],R[j],Rt); }
}

void heap(RECORD **R, int N) {
		int i, j, l, r, Kt;
		RECORD *Rt = (RECORD *)malloc(sizeof(RECORD));

H1:		l=N/2+1; r=N;
H2:		if (l>1) { l-=1; Rt=R[l]; Kt=R[l]->K; }
		else { Rt=R[r]; Kt=R[r]->K; R[r]=R[1]; r-=1;
			if (r==1) { R[1]=Rt; goto END; } }
H3:		j=l;
H4:		i=j; j*=2; if (j<r) goto H5; if (j==r) goto H6; if (j>r) goto H8;
H5:		if (R[j]->K<R[j+1]->K) j+=1;
H6:		if (Kt>=R[j]->K) goto H8;
H7:		R[i]=R[j]; goto H4;
H8:		R[i]=Rt; goto H2;
END:            ;
}

void tmerge(RECORD **R, int N) {
		int i, j, k, m, n;
		RECORD **x, **y, **z;

		m = n = N/2;
		x = (RECORD **)malloc((m+1)*sizeof(RECORD *));
		for (i=1; i<=m; i++) {
			x[i] = (RECORD *)malloc(sizeof(RECORD));
			x[i]->K = R[i]->K; x[i]->L = i;
		}
		ins(x, N/2);
		y = (RECORD **)malloc((n+1)*sizeof(RECORD *));
		for (j=1; j<=n; j++) {
			y[j] = (RECORD *)malloc(sizeof(RECORD));
			y[j]->K = R[j+i-1]->K; y[j]->L = j;
		}
		ins(y, N/2);
		z = R;

M1:		i=1; j=1; k=1;
M2:		if (x[i]->K<=y[j]->K) goto M3; else goto M5;
M3:		z[k]->K=x[i]->K; k+=1; i+=1; if (i<=m) goto M2;
M4:		while (k<=m+n || j<=n) z[k++]->K=y[j++]->K; goto END;
M5:		z[k]->K=y[j]->K; k+=1; j+=1; if (j<=n) goto M2;
M6:		while (k<=m+n || i<=m) z[k++]->K=x[i++]->K; goto END;
END:            ;
}

void ntmerge(RECORD **R, int N) {
		int i, j, l, d, f, s, t, k;

		for (i=N+1; i<=2*N; i++) {
			R[i] = (RECORD *)malloc(sizeof(RECORD));
			R[i]->L = i;
		}

N1:		s=0;
N2:		if (s==0) { i=1; j=N; k=N+1; l=2*N; }
		if (s==1) { i=N+1; j=2*N; k=1; l=N; }
		d=1; f=1;
N3:		if (R[i]->K>R[j]->K) goto N8; if (i==j) { R[k]=R[i]; goto N13; }
N4:		R[k]=R[i]; k+=d;
N5:		i+=1; if (R[i-1]->K<=R[i]->K) goto N3;
N6:		R[k]=R[j]; k+=d;
N7:		j-=1; if (R[j+1]->K<=R[j]->K) goto N6; else goto N12;
N8:		R[k]=R[j]; k+=d;
N9:		j-=1; if (R[j+1]->K<=R[j]->K) goto N3;
N10:	R[k]=R[i]; k+=d;
N11:	i+=1; if (R[i-1]->K<=R[i]->K) goto N10;
N12:	f=0; d=-d; t=k; k=l; l=t; goto N3;
N13:	if (f==0) { s=1-s; goto N2; }
		if (s==0) for (t=1; t<=N; t+=1) { R[t]=R[t+N]; }
}

void stmerge(RECORD **R, int N) {
		int i, j, k, l, d, p, q, r, s, t;

		for (i=N+1; i<=2*N; i++) {
			R[i] = (RECORD *)malloc(sizeof(RECORD));
			R[i]->L = i;
		}

S1:		s=0; p=1;
S2:		if (s==0) { i=1; j=N; k=N; l=2*N+1; }
		if (s==1) { i=N+1; j=2*N; k=0; l=N+1; }
		d=1; q=p; r=p;
S3:		if (R[i]->K>R[j]->K) goto S8;
S4:		k=k+d; R[k]=R[i];
S5:		i+=1; q-=1; if (q>0) goto S3;
S6:		k+=d; if (k==l) goto S13; else R[k]=R[j];
S7:		j-=1; r-=1; if (r>0) goto S6; else goto S12;
S8:		k+=d; R[k]=R[j];
S9:		j-=1; r-=1; if (r>0) goto S3;
S10:	k+=d; if (k==l) goto S13; else R[k]=R[i];
S11:	i+=1; q-=1; if (q>0) goto S10;
S12:	q=p; r=p; d=-d; t=k; k=l; l=t; if (j-i<p) goto S10; else goto S3;
S13:	p+=p; if (p<N) { s=1-s; goto S2; }
		if (s==0) for (t=1; t<=N; t+=1) { R[t]=R[t+N]; }
}

void lmerge(RECORD **R, int N) {
		int i, p, q, s, t;

		R[N+1] = (RECORD *)malloc(sizeof(RECORD));

L1:		R[0]->L=1; R[N+1]->L=2;
		for (i=1; i<=N-2; i++) R[i]->L=-(i+2);
		R[N-1]->L=R[N]->L=0;
L2:		s=0; t=N+1; p=R[s]->L; q=R[t]->L;
		if (q==0) goto END;
L3:		if (R[p]->K>R[q]->K) goto L6;
L4:		R[s]->L=set(R[s]->L,p); s=p; p=R[p]->L; if (p>0) goto L3;
L5:		R[s]->L=q; s=t; while (q>0) { t=q; q=R[q]->L; } goto L8;
L6:		R[s]->L=set(R[s]->L,q); s=q; q=R[q]->L; if (q>0) goto L3;
L7:		R[s]->L=p; s=t; while (p>0) { t=p; p=R[p]->L; }
L8:		p=-p; q=-q; if (q==0) { R[s]->L=set(R[s]->L,p); R[t]->L=0; goto L2; }
		else goto L3;
END:            ;
}

void fill(RECORD **R, int N) {
	int i;

	srand(time(NULL));
	R[0]->K = N;
	R[0]->L = 0;
	for (i=1; i<=N; i++) {
		R[i]->K = u + (rand()%(v-u+1));
		R[i]->L = i;
	}
}

void printarray(RECORD **R, int N) {
	int i;

	for (i=0; i<=N; i++) {
		printf("i: %3d\tR->K: %3d\tR->L: %3d\n", i, R[i]->K, R[i]->L);
	}
}

void printlist(RECORD **R) {
	int i;

	i = 0;
	do {
		printf("i: %3d\tR->K: %3d\tR->L: %3d\n", i, R[i]->K, R[i]->L);
		i=R[i]->L;
	} while (R[i]->L);
}

int lg(int i, ROUND r) {
	int a;
	double b;

	a = (int)(log10((double)i)/log10(2));
	b = log10((double)i)/log10(2);
	if ((double)a < b)
		if (r) a+=1;
	return a;
}

void fatal(char *msg) {
	fprintf(stderr, "ERROR: %s\n", msg);
	exit(1);
}

void usage(void) {
	printf(
                "Usage:\n"
                "  a.out [options]\n"
                "Options:\n"
                "  -c   Comparison counting\n"
                "  -d   Distribution counting\n"
                "  -i   Straight insertion\n"
                "  -e   Shell's method\n"
                "  -l   List insertion\n"
                "  -b   Bubble sort\n"
                "  -m   Merge exchange\n"
                "  -q   Quicksort\n"
                "  -r   Radix exchange sort\n"
                "  -s   Straight selection sort\n"
                "  -h   Heapsort\n"
                "  -t   Two-way merge\n"
                "  -n   Natural two-way merge sort\n"
                "  -g   Straight two-way merge sort\n"
                "  -w   List merge sort\n"
        );
	exit(0);
}