#include <iostream>
#include <vector>
using namespace std;

void scal(vector<int>& tab, int pocz, int kon) {
    cout << pocz << " " << kon << endl;
    int mid = (pocz + kon) / 2;
    vector<int> part1(mid - pocz + 1);
    vector<int> part2(kon - mid);

    for (int i = pocz; i <= mid; i++)
        part1[i - pocz] = tab[i];
    
    for (int i = mid + 1; i <= kon; i++) {
        part2[i - (mid + 1)] = tab[i];
    }

    int i1 = 0;
    int i2 = 0;

    while (i1 < part1.size() && i2 < part2.size()) {
        if (part1[i1] < part2[i2]) {
            tab[pocz + i1 + i2] = part1[i1];
            i1++;
        }
        else {
            tab[pocz + i1 + i2] = part2[i2];
            i2++;
        }
    }

    while (i1 < part1.size()) {
        tab[pocz + i1 + i2] = part1[i1];
        i1++;
    }

    while (i2 < part2.size()) {
        tab[pocz + i1 + i2] = part2[i2];
        i2++;
    }
/*    for(auto e : tab){
    	cout << e << " ";
    }
    cout << endl << endl;
*/
}

void sortowaniePrzezScalanie(vector<int>& tab, int pocz, int kon) {
    // posortuj tablice w przedziale <pocz : kon>
    
    // warunek brzegowy -> rozmiar 1
    if (pocz == kon) {
        return;
    }

    int mid = (pocz + kon) / 2;

    sortowaniePrzezScalanie(tab, pocz, mid);
    sortowaniePrzezScalanie(tab, mid + 1, kon);

    scal(tab, pocz, kon);
    for(auto e : tab){
    	cout << e << " ";
    }
    cout << endl << endl;
}


int main() {
	vector <int> tab{2,1,5,4,3};
	sortowaniePrzezScalanie(tab, 0, 4);
	for(auto elem : tab){
//		cout << elem << " ";
	}
	
	return 0;
}