/**
 *  Quick Sort ANSI C implementation
 *  Copyright (C) 2010 Matous Jan Fialka, <http://mjf.cz/>
 *  Released under the terms of The MIT License
 */

void
qsort(int a[], int l, int r)
{
	int i = l - 1, j = r, k, p = l - 1, q = r, z, v = a[r];

	if(r <= l)
		return;
	while(1) {
		while(a[++i] < v) ;
		while(v < a[--j])
			if(j == l)
				break;
		if(i >= j)
			break;
		z = a[i];
		a[i] = a[j];
		a[j] = z;;
		if(a[i] == v) {
			p++;
			z = a[p];
			a[p] = a[i];
			a[i] = z;;
		}
		if(v == a[j]) {
			q--;
			z = a[j];
			a[j] = a[q];
			a[q] = z;;
		}
	}
	z = a[i];
	a[i] = a[r];
	a[r] = z;;
	j = i - 1;
	i = i + 1;
	for(k = l; k < p; k++, j--) {
		z = a[k];
		a[k] = a[j];
		a[j] = z;;
	}
	for(k = r - 1; k > q; k--, i++) {
		z = a[i];
		a[i] = a[k];
		a[k] = z;;
	}
	qsort(a, l, j);
	qsort(a, i, r);
	return;
}