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

int
median(int ar[], int no)
{
	int hi, lo, md, mi, ll, hh, tp;

	lo = mi = ll = hh = tp = 0;
	hi = no - 1;
	md = (lo + hi) / 2;
L00:
	if(hi <= lo)
		goto L10;
	if(hi != lo + 1)
		goto L01;
	if(ar[lo] <= ar[hi])
		goto L10;
	tp = ar[lo];
	ar[lo] = ar[hi];
	ar[hi] = tp;
L01:
	mi = (lo + hi) / 2;
	if(ar[mi] <= ar[hi])
		goto L02;
	tp = ar[mi];
	ar[mi] = ar[hi];
	ar[hi] = tp;
L02:
	if(ar[lo] <= ar[hi])
		goto L03;
	tp = ar[lo];
	ar[lo] = ar[hi];
	ar[hi] = tp;
L03:
	if(ar[mi] <= ar[lo])
		goto L04;
	tp = ar[mi];
	ar[mi] = ar[lo];
	ar[lo] = tp;
L04:
	tp = ar[mi];
	ar[mi] = ar[lo + 1];
	ar[lo + 1] = tp;
	ll = lo + 1;
	hh = hi;
L05:
	ll = ll + 1;
	if(ar[lo] > ar[ll])
		goto L05;
L06:
	hh = hh - 1;
	if(ar[hh] > ar[lo])
		goto L06;
	if(hh < ll)
		goto L07;
	tp = ar[ll];
	ar[ll] = ar[hh];
	ar[hh] = tp;
	goto L05;
L07:
	tp = ar[lo];
	ar[lo] = ar[hh];
	ar[hh] = tp;
	if(hh > md)
		goto L08;
	lo = ll;
L08:
	if(hh < md)
		goto L09;
	hi = hh - 1;
L09:
	goto L00;
L10:
	return ar[md];
}

#define N 100000000

int
main(void)
{
	int i, *a = 0;

	a = (int *)malloc(N * sizeof(int));
	if(!a) {
		fprintf(stderr, "Not enough memory, sorry.\n");
		return 0;
	}
	printf("Generating %d random values... ", N);
	srand(time(0));
	for(i = 0; i <= N; i++)
		a[i] = rand() % N;
	printf("done.\n");
	printf("Calculating median value... ");
	i = median(a, N);
	printf("done.\n");
	printf("Median value is %d.\n", i);
	return 0;
}