#include <iostream>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <vector>

void swap( vector<int>::iterator p, vector<int>::iterator q)
{	int pv = *p;
	*p=*q;
	*q=pv;
}
void sort( vector<int>::iterator begin, vector<int>::iterator end)
{
  // a simple and peculiar version of Tony Hoare's famous QuickSort algorithm
  /*
	(1) Partition vector into two parts so that one is less than the other
	(2) Sort each part using the same algorithm
  */

  if(begin+1 >= end )
  {
    // zero or one element are already sorted!
	return;
  }else if(begin+2==end)
  {
    // two elements
	if( *begin > *(begin+1) )
		swap(begin, begin+1);
  }else //  more than 2 elements
  {
/* debugging
	for(vector<int>::iterator p=begin; p!=end; p++)
		cerr << *p << " ";
	cerr << endl;
*/
    // pick a random value in the vector called the "pivot".
	int pivot_position=rand()%(end-begin);
 //       cerr << pivot_position << endl;
	int value = *(begin + pivot_position);

    // Split array so that first part are <= the value, and the rest > value
        vector<int>::iterator split;
	split=partition(begin, end, bind2nd(less_equal<int>(), value));

    // split is the first item that is > value
/*
	for(vector<int>::iterator p=begin; p!=end; p++)
	{
		if(p==split)
			cerr << " | ";
		cerr << *p << " ";
	}
	cerr << endl;
*/
	if(split == end) // all elements are <= value
	{
		if(count(begin, end, value) == end-begin)//all equal!
			return;
		else
			sort(begin, split);
	}else
	{
		sort(begin, split);//at least one element is <= value.
		sort(split, end);
	}
  }
}

int main()
{
   const int seed = static_cast<int>(time(0));
   srand(seed);//set random numbers differently each run

   const int Biggest = 100000;
   const int Size = 500000;
   const int Sample = 100;

   double total_time =0.0;
   double max_time =0.0;
   double sum_squares=0.0;

   for(int s = 0; s<Sample; s++)
   { 
      vector <int> data;
      for(int i = 0; i< Size; i++)
      {
	   data.push_back(rand()%Biggest);
      }

      time_t time1 = time(0);
      sort(data.begin(), data.end());
      time_t time2 = time(0);
      
      double time_difference= difftime(time2, time1);
      total_time+= time_difference;
      sum_squares+= time_difference*time_difference;
      if(time_difference > max_time)
		max_time=time_difference;
   }

   cout << "Size =" << Size << ", mean time =";
   double mean_time= total_time /Sample ;
   cout << mean_time;
   cout << ", Max time =" << max_time;
   cout << ", Standard Deviation ="<< sqrt(sum_squares/Sample - mean_time*mean_time);
   cout<<endl;

   return 0;
}