#include <iostream>
#include <ctime>
#include <vector>
#include <stack>
#include <utility>
#include <algorithm>

using namespace std;

namespace amv	{

//*** Algoritmo quicksort que usa un vector e índices (más didáctico)

//Función auxiliar
inline int quicksort_partition1(vector<int> &v, int first, int last)
{
int p=first+(last-first)/2;
int value=v[p];
swap(v[p],v[last]);

int bottom=first, top=last-1;

for(;;)
	{
	while(v[bottom]<=value && bottom<=top) ++bottom;
	while(v[top]>=value && bottom<=top) --top;

	if(bottom<top)
		swap(v[bottom],v[top]);
	else
		break;
	}

swap(v[last],v[bottom]);

return bottom;
}

//Función principal
inline void quicksort1(vector<int> &v)
{
stack<pair<int,int> > sIndexes;
pair<int,int> indexes;
int p;

sIndexes.push(make_pair(0,v.size()-1));

while(!sIndexes.empty())
	{
	indexes=sIndexes.top();
	sIndexes.pop();
	if(indexes.first<indexes.second)
		{
		p=quicksort_partition1(v,indexes.first,indexes.second);
		sIndexes.push(make_pair(p+1,indexes.second));
		sIndexes.push(make_pair(indexes.first,p-1));
		}
	}
}

//*** Algoritmo quicksort que usa iteradores (una secuencia), más rápido que el anterior 

//Función auxiliar
template <class It>
inline It quicksort_partition(It first, It last)
{
It p=first+(last-first)/2;
int value=*p;
iter_swap(p,last);

It bottom=first, top=last-1;

for(;;)
	{
	while(*bottom<=value && bottom<=top) ++bottom;
	while(*top>=value && bottom<=top) --top;

	if(bottom<top)
		iter_swap(bottom,top);
	else
		break;
	}

iter_swap(last,bottom);

return bottom;
}

//Función principal
template <class It>
inline void quicksort(It first, It last)
{
stack<pair<It,It> > sIndexes;
pair<It,It> indexes;
It p;

sIndexes.push(make_pair(first,last-1));

while(!sIndexes.empty())
	{
	indexes=sIndexes.top();
	sIndexes.pop();
	if(indexes.first<indexes.second)
		{
		p=quicksort_partition(indexes.first,indexes.second);
		sIndexes.push(make_pair(p+1,indexes.second));
		sIndexes.push(make_pair(indexes.first,p-1));
		}
	}
}

}

//************************* Bloque principal

void main()
{
time_t t1,t2;
vector<int> v;
int n, items=2000000;

for(int i=0; i<items; ++i)
	{
	n=items-i;
	v.push_back(n);
	}

cerr<<time(&t1)<<'\n';

//amv::quicksort1(v); //Lento

amv::quicksort(v.begin(),v.end()); //Rápido

//sort(v.begin(),v.end()); //Muy rápido

/* Quite las marcas de comentario si quiere imprimir los elementos
for(i=0; i<items; ++i)
	{
	cerr<<v[i]<<' ';
	}
*/

time(&t2);
cerr<<"\nTiempo transcurrido: "<<(t2-t1)<<'\n';

}