#include "pch.h"
#include <iostream>
#include <vector>

using namespace std;

void wys(vector<int>tab)
{
    for (int i = 0; i < tab.size(); i++)
    {
        cout << tab[i] << ", ";
    }
    cout << endl;
}


void scalanie(vector<int>&lewa, vector<int>&prawa, vector<int>&tab)
{
    int nL = lewa.size();
    int nR = prawa.size();
    int i = 0, j = 0, k = 0;

    while (j < nL && k < nR)
    {
        if (lewa[j] < prawa[k])
        {
            tab[i] = lewa[j];
            j++;
        }
        else
        {
            tab[i] = prawa[k];
            k++;
        }
        i++;
    }
    while (j < nL)
    {
        tab[i] = lewa[j];
        j++; i++;
    }
    while (k < nR)
    {
        tab[i] = prawa[k];
        k++; i++;
    }
}

void sort(vector<int>&tab)
{
    if (tab.size() <= 1) return;

    int sr = tab.size() / 2;
    vector<int>lewa;
    vector<int>prawa;

    for (int i = 0; i < sr; i++)
    {
        lewa.push_back(tab[i]);
        //cout << lewa[i] << ", ";
    }
    //cout <<"  ";
    for (int i = 0; i < tab.size() - sr; i++)
    {
        prawa.push_back(tab[sr + i]);
        //cout  << prawa[i] << ", ";
    }
    //cout << "  ";
    sort(lewa);
    sort(prawa);
    //cout << endl;
    scalanie(lewa, prawa, tab);

}
int main()
{
    vector<int>tab;
    for (int i = 0; i < 1000000; i++)
    {
        tab.push_back(rand() % 100);
        //cout << tab[i] << endl;
    }


    sort(tab);
    //wys(tab);
    cout << "Koniec";
    system("pause");
}