/*
	Quick Sort Algorithm, Written By Veselin Georgiev
*/

static inline void swp(int *a, int *b) { int t = *a; *a = *b; *b = t; }

int partition(int a[], int l, int r, int x)
{
	int i, j;
	int t = l;
	for (i = l; i <= r; i++) if (a[i] < x) t++;
	swp(a+t, a+ ((l+r)/2));
	i = l;
	j = r;
	while (i < t || j > t) {
		while (i < t && a[i] < x) i++;
		while (j > t && a[j] >= x) j--;
		if (i < t || j > t) {
			swp(a+i, a+j);
			i++; j--;
		}
	}
	return t;
}

void sort(int a[], int l, int r)
{
	int x, t;
	if (l >= r) return;
	x = a[(l + r) / 2];
	t = partition(a, l, r, x);
	sort(a, l, t-1);
	sort(a, t+1, r);
}

void quick_sort(int a[], int n)
{
	sort(a, 0, n-1);
}