// Bombinski

void swap( int[], int, int);
void bubblesort(int [], int, int);
void sort(int [], int);
void quicksort(int [], int, int);
void quickbubblesort(int [], int);



#define CROSSOVER	6

void swap(int a[], int i, int j)
{
	int T;
	T = a[i]; 
	a[i] = a[j];
	a[j] = T;
}

void bubblesort(int a[], int lo, int hi)
{
	int i, j, temp, flag;

	for (i = hi; i >= lo; i--) {
		flag = 0;
		for(j = lo; j < i; j++) {
			if (a[j] > a[j+1]) {
				swap(a, j, j+1);
				flag++;
			}
		}
		if (flag == 0) return;
    }
}

void sort(int a[], int size)
{
	int i, j, v;
	int left = 0, right = size-1;
	if (right - left <= CROSSOVER) {
		bubblesort(a, left, right);
	} else {
		/* Use the tri-median method to find a "decent" pivot
value */
		i = (left + right)/2;
		if (a[left]>a[i]) swap(a,left,i);
		if (a[left]>a[right]) swap(a,left,right);
		if (a[i]>a[right]) swap(a,i,right);

		j = right - 1;
		swap(a,i,j);

		i = left;
		v = a[j];

		for(;;)
		{
			while(a[++i] < v);
			while(a[--j] > v);
			if (j<i) break;
			swap (a,i,j);
		}
		swap(a,i,right - 1);

		quicksort(a,left,j);
		quicksort(a,i+1,right);
	}
}

/* Sort array a[] of n integers using quick sort */
void quickbubblesort(int a[], int n) 
{
	if (n<=1) return;
	quicksort(a, 0, n-1);
}

void quicksort(int a[], int left, int right)
{
	int i, j, v;

	if (right - left <= CROSSOVER) {
		bubblesort(a, left, right);
	} else {
		/* Use the tri-median method to find a "decent" pivot
value */
		i = (left + right)/2;
		if (a[left]>a[i]) swap(a,left,i);
		if (a[left]>a[right]) swap(a,left,right);
		if (a[i]>a[right]) swap(a,i,right);

		j = right - 1;
		swap(a,i,j);

		i = left;
		v = a[j];

		for(;;)
		{
			while(a[++i] < v);
			while(a[--j] > v);
			if (j<i) break;
			swap (a,i,j);
		}
		swap(a,i,right - 1);

		quicksort(a,left,j);
		quicksort(a,i+1,right);
	}
}