******** fig7.16 **********

	/* q_select places the kth smallest element in a[k] */
	void
	q_select( input_type a[], int k, int left, int right )
	{
		int i, j;
		input_type pivot;

/*1*/		if( left + CUTOFF <= right )
		{
/*2*/			pivot = median3( a, left, right );
/*3*/			i=left; j=right-1;
/*4*/			for(;;)
			{
/*5*/				while( a[++i] < pivot );
/*6*/				while( a[--j] > pivot );
/*7*/				if( i < j )
/*8*/					swap( &a[i], &a[j] );
				else
/*9*/					break;
			}
/*10*/			swap( &a[i], &a[right-1] );	/* restore pivot */

/*11*/			if( k < i )
/*12*/				q_select( a, k, left, i-1 );
			else
/*13*/			if( k > i )
/*14*/				q_select( a, k, i+1, right );
		}
		else
/*15*/			insert_sort( a, left, right );
	}