#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define	TT 16
/****Copyright (c) 1997,1998,1999-2002 All rights reserved
 ****A. V. Gerbessiotis 
 ****Permission to use, copy, modify, and distribute this software,
 ****and to incorporate it, in whole or in part, into 
 ****other software,is hereby granted without fee, provided that
 ****  (1) the above copyright notice and this permission 
 ****      notice appear in all copies of the source code, and 
 ****      the above copyright notice appear in clearly visible 
 ****      form on all supporting documentation and distribution 
 ****      media, and
 ****     (2) any redistribution of the software, in original
 ****         or modified form, be without fee and subject to
 ****         these same conditions.
 ****   No guarantee, whatsoever, is offered that the code works as
 ****   advertised or is absent of any, even damaging,
 ****   side-effects. Use this code at your own personal risk.
 ****/


void inseti();

void quick_2_sort(int *keys, int n, int l,int r)
{
	register int i,j;
	int  x,y;

	i=l;j=r;
 	x=keys[(l+r)/2];

do
{
	while (keys[i]<x) i++;
	while (x<keys[j]) j--;
	if (i <= j )
	{
		y=keys[i];
		keys[i]=keys[j];
		keys[j]=y;
		i++;j--;
	}
} while (i <= j);
	
	if (l < j)
		if ((j-l) < TT)
			 inserti(&keys[l],(j-l+1));
		else
			quick_2_sort(keys,n,l,j);
	if (i < r)
		if ((r-i) < TT)
			 inserti(&keys[i],(r-i+1));
		else
			quick_2_sort(keys,n,i,r);
	
}

void quick2i(int *keys, int n)
{
		quick_2_sort(keys,n,0,n-1);
}
