#include <stdio.h>
#include <time.h>
#include <iostream>
#include <cstdlib>
#include <chrono>

using namespace std;
const int arr_size = 10000;
const int col_razr = 3;

int velich_razr(int chislo, int razr)
{
    while (razr>1)
    {
        chislo /= 10;
        razr--;
    }
    return chislo % 10;
}

void sort_razr(int** tempArray, int* mas, int razr, int* mas_col)
{
    int temp = 0, a = 0;

    for (int i = 0; i < arr_size; i++)
    {
        mas_col[i] = 0;
    }

    for (int i = 1; i < arr_size; i++)
    {
        a = velich_razr(mas[i], razr);
        tempArray[mas_col[a]][a] = mas[i];
        mas_col[a]++;
    }

    for (int i = 0; i < arr_size; i++)
    {
        for (int j = 0; j < mas_col[i]; j++)
        {
            mas[temp] = tempArray[j][i];
            temp++;
        }
    }
}

////////////////////////////

void Merge(int *A, int first, int last)
{
    int middle, start, final;
    int *arr = new int[arr_size];

    middle = (first + last) / 2;                        //вычисление среднего элемента
    start = first;                                      //начало левой части
    final = middle + 1;                                 //начало правой части

    for (int j = first; j <= last; j++)                 //выполнять от начала до конца
    {
        if ((start <= middle) && ((final > last) || (A[start] < A[final])))
        {
            arr[j] = A[start];
            start++;
        }
        else
        {
            arr[j] = A[final];
            final++;
        }
    }

    //возвращение результата в список

    for (int j = first; j <= last; j++)
    {
        A[j] = arr[j];
    }

    delete[]arr;
};

//рекурсивная процедура сортировки

void MergeSort(int *A, int first, int last)
{
    {
        if (first<last)
        {
            MergeSort(A, first, (first + last) / 2);    //сортировка левой части
            MergeSort(A, (first + last) / 2 + 1, last); //сортировка правой части
            Merge(A, first, last);                      //слияние двух частей
        }
    }
};


void main() {

    int razr;
    int* mas_col = new int[arr_size];
    int** tempArray = new int*[arr_size];
    int* mainArray = new int[arr_size];
    int* secondMainArray = new int[arr_size];


    for (int i = 1; i <= arr_size - 1; i++)
    {
        mainArray[i] = rand() % 1000;           // запись случайного числа до 1000, которое вернет rand()
        secondMainArray[i] = mainArray[i];
    }

    for (int i = 0; i < arr_size; i++)
    {
        tempArray[i] = new int[arr_size];
    }

    auto firstSortStart = chrono::steady_clock::now();

    for (razr = 1; razr < 4; razr++)
    {
        sort_razr(tempArray, mainArray, razr, mas_col);
    }

    printf("\nFirst sorting:\n");

    for (int i = 0; i <= arr_size - 1; i++)
    {
        //cout << mainArray[i] << endl;
        cout << ".";
    }

    auto firstSortEnd = chrono::steady_clock::now();

    auto secondSortStart = chrono::steady_clock::now();

    MergeSort(secondMainArray, 0, arr_size - 1);

    printf("\nSecond sorting:\n");

    for (int i = 0; i <= arr_size - 1; i++)
    {
        //cout << secondMainArray[i] << endl;

        cout << ".";
    }

    auto secondSortEnd = chrono::steady_clock::now();

    auto elapsed_ms1 = chrono::duration_cast<chrono::milliseconds>(firstSortEnd - firstSortStart);
    auto elapsed_ms2 = chrono::duration_cast<chrono::milliseconds>(secondSortEnd - secondSortStart);

    cout << "\nFirst sort time: " << elapsed_ms1.count() << " ms\n";
    cout << "\nSecond sort time: " << elapsed_ms2.count() << " ms\n";

    for (int i = 0; i < arr_size; i++) {
        delete[] tempArray[i];
    }

    delete[] mas_col;
    delete[] mainArray;
    delete[] secondMainArray;
    delete[] tempArray;

    system("pause");

}