#include <iostream>
#include <array>
#include <chrono>
#include <algorithm>

const long int g_arrayElements = 631000;

class Timer
{
private:

	using clock_t = std::chrono::high_resolution_clock;
	using second_t = std::chrono::duration<double, std::ratio<1> >;

	std::chrono::time_point<clock_t> m_beg;

public:
	Timer() : m_beg(clock_t::now())
	{
	}

	void reset()
	{
		m_beg = clock_t::now();
	}

	double elapsed() const
	{
		return std::chrono::duration_cast<second_t>(clock_t::now() - m_beg).count();
	}
};

void InsertionSort(std::array<long int, g_arrayElements> &array)
{
     for (long int i = 1; i < g_arrayElements; i++) {
        for (long int j = i; j > 0 && array[j - 1] > array[j]; j--) {
            long int tmp = array[j];
            array[j] = array[j - 1];
            array[j - 1] = tmp;
        }
    }
}
int digit(long int n, long int p) //получение p-го байта
{
  return (n >> (8 * p) & 255);
}
void RadixSort(std::array<long int, g_arrayElements> &array)
{   long int b[g_arrayElements];
    int k = sizeof(int);
    for(int i = 0; i < k; i++) {
      int c[256] = {0};
      for(long int j = 0; j < g_arrayElements; j++)
      {
        c[digit(array[j],i)]++;
      }
      for(int j = 1; j < 256;j++) {
        c[j] += c[j-1];
      }
      for(long int j = g_arrayElements - 1; j >-1;j--){
        b[--c[digit(array[j], i)]] = array[j];
      }
    for (long int j = 0; j < g_arrayElements; j++) {
        array[j] = b[j];
      }
    }
}

void merge(std::array<long int, g_arrayElements> &array, long int l, long int m, long int r){
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;
    int L[n1], R[n2];

    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++)
        L[i] = array[l + i];
    for (j = 0; j < n2; j++)
        R[j] = array[m + 1+ j];

    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            array[k] = L[i];
            i++;
        }
        else
        {
            array[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1)
    {
        array[k] = L[i];
        i++;
        k++;
    }

    while (j < n2)
    {
        array[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(std::array<long int, g_arrayElements> &array, int l, int r)
{
    if (l < r)
    {
        int m = l+(r-l)/2;
        mergeSort(array, l, m);
        mergeSort(array, m+1, r);
        merge(array, l, m, r);
    }
}

void Hoara(std::array<long int, g_arrayElements> &array, long int first, long int last){
    int mid, count;
    int f=first, l=last;
    mid=array[f + (l - f) / 2];
    do
    {
    while (array[f]<mid) f++;
    while (array[l]>mid) l--;
    if (f<=l)
    {
        count=array[f];
        array[f]=array[l];
        array[l]=count;
        f++;
        l--;
    }
    } while (f<l);
    if (first<l) Hoara(array, first, l);
    if (f<last) Hoara(array, f, last);
    }

int main()
{
    std::array<long int, g_arrayElements> array;
    std :: cout << "Sort:" << '\n';
    for(int m = 0; m < 1; m++){
    Timer t;
	//std::array<long int, g_arrayElements> array;
	long int *mas = new long int[g_arrayElements];
    std :: mt19937 gen(time(0));
    std :: uniform_int_distribution<long int>uid(0, 100000);
  for (long int i = 0; i < g_arrayElements ; i++) {
    mas[i] = uid(gen);
  }
	std::sort(&mas[0], &mas[g_arrayElements]);
    delete [] mas;
	std::cout << "Time taken: " << t.elapsed() << '\n';
    }
    std :: cout << '\n'<< '\n' << "Insertion Sort:"<< '\n';
    for(int m = 0; m < 1; m++){
    Timer t;
	//std::array<long int, g_arrayElements> array;
    std :: mt19937 gen(time(0));
    std :: uniform_int_distribution<long int>uid(0, 100000);
    for (long int i = 0; i < g_arrayElements ; i++) {
        array[i] = uid(gen);
    }
    InsertionSort(array);
    std::cout << "Time taken: " << t.elapsed() << '\n';
    }
    std :: cout << '\n'<< '\n' << "Radix Sort:"<< '\n';
    for(int m = 0; m < 1; m++){
    Timer t;
	//std::array<long int, g_arrayElements> array;
    std :: mt19937 gen(time(0));
    std :: uniform_int_distribution<long int>uid(0, 100000);
    for (long int i = 0; i < g_arrayElements ; i++) {
        array[i] = uid(gen);
    }
    RadixSort(array);
    std::cout << "Time taken: " << t.elapsed() << '\n';
    }
    //std::array<long int, g_arrayElements> array;
    std :: cout << '\n'<< '\n' << "Merge Sort:"<< '\n';
    for(int m = 0; m < 7; m++){
    Timer t;
	std :: mt19937 gen(time(0));
    std :: uniform_int_distribution<long int>uid(0, 100000);
    for (long int i = 0; i < g_arrayElements ; i++) {
        array[i] = uid(gen);
    }
    mergeSort(array, 0, g_arrayElements - 1);
    std::cout << "Time taken: " << t.elapsed() << '\n';
    }
    std :: cout << '\n'<< '\n' << "Hoara Sort:"<< '\n';
    for(int m = 0; m < 7; m++){
    Timer t;
	std :: mt19937 gen(time(0));
    std :: uniform_int_distribution<long int>uid(0, 100000);
    for (long int i = 0; i < g_arrayElements ; i++) {
        array[i] = uid(gen);
    }
    Hoara(array, 0, g_arrayElements - 1);
    std::cout << "Time taken: " << t.elapsed() << '\n';
    }
	return 0;
}