// O(n log(n))
void quickSort ( vector <int > & v) {
	quickSort (v , 0, v. size () -1);
}

void quickSort ( vector <int > & v , int a , int b ) {
	int p, q;
	if ( a <= b ) {
		particion (v , a , b , v[a], p, q);
		quickSort (v , a , p -1);
		quickSort (v , p +1 , b );
	}
}

// P: { 0 <= a <= b +1 <= v . size () }
// I : a <= p <= k <= q +1 <= b +1 <= v . size () && menores (v ,a ,p -1) && iguales (v ,p ,k -1) && mayores (v , q +1 , b )
// Q : { a <= p <= q +1 <= b +1 <= v . size () /\ menores (v ,a ,p -1) /\ iguales (v ,p , q ) /\ mayores (v , q +1 , b )

void particion(vector <int> & v, int a, int b, int pivote , int& p, int& q) {
	int k = a, aux;
	p = a;  
	q = b;
	while (k <= q) {
		if (v[k] == pivote) k++;
		else if (v[k] < pivote) {
		 	aux = v[p];
			v[p] = v[k];
			v[k] = aux;
			p++;
			k=++;
		}
		else {
			aux = v[q];
			v[q] = v[k];
			v[k] = aux;
			q--;
	 	}
	} 
}

// O(n log(n))
void mergeSort ( vector <int > & v) {
	mergeSort (v , 0, v. size () -1);
}

void mergeSort ( vector <int > & v , int a , int b ) {
	int m;
	if ( a < b ) {
		m = ( a+b) / 2;
		mergeSort ( v , a , m );
		mergeSort ( v , m +1 , b );
		mezcla ( v , a , m , b );
	}
}

// O(log n)
int buscaBin ( vector <int > const & v , int x , int c , int f ) {
	int p , m ;
	if ( c == f +1 ) p = c - 1; 
	else { // c <= f
		m = ( c+f) / 2;
		if ( v[m ] <= x ) p = buscaBin ( v , x , m +1 , f ); 
		else p = buscaBin ( v , x , c , m -1 ); 
	return p;
}

int buscaBin ( vector <int > const & v , int x )
	{ return buscaBin (v ,x ,0 , v. size () -1); }