#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;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdm9pZCBzY2FsKHZlY3RvcjxpbnQ+JiB0YWIsIGludCBwb2N6LCBpbnQga29uKSB7CiAgICBjb3V0IDw8IHBvY3ogPDwgIiAiIDw8IGtvbiA8PCBlbmRsOwogICAgaW50IG1pZCA9IChwb2N6ICsga29uKSAvIDI7CiAgICB2ZWN0b3I8aW50PiBwYXJ0MShtaWQgLSBwb2N6ICsgMSk7CiAgICB2ZWN0b3I8aW50PiBwYXJ0Mihrb24gLSBtaWQpOwoKICAgIGZvciAoaW50IGkgPSBwb2N6OyBpIDw9IG1pZDsgaSsrKQogICAgICAgIHBhcnQxW2kgLSBwb2N6XSA9IHRhYltpXTsKICAgIAogICAgZm9yIChpbnQgaSA9IG1pZCArIDE7IGkgPD0ga29uOyBpKyspIHsKICAgICAgICBwYXJ0MltpIC0gKG1pZCArIDEpXSA9IHRhYltpXTsKICAgIH0KCiAgICBpbnQgaTEgPSAwOwogICAgaW50IGkyID0gMDsKCiAgICB3aGlsZSAoaTEgPCBwYXJ0MS5zaXplKCkgJiYgaTIgPCBwYXJ0Mi5zaXplKCkpIHsKICAgICAgICBpZiAocGFydDFbaTFdIDwgcGFydDJbaTJdKSB7CiAgICAgICAgICAgIHRhYltwb2N6ICsgaTEgKyBpMl0gPSBwYXJ0MVtpMV07CiAgICAgICAgICAgIGkxKys7CiAgICAgICAgfQogICAgICAgIGVsc2UgewogICAgICAgICAgICB0YWJbcG9jeiArIGkxICsgaTJdID0gcGFydDJbaTJdOwogICAgICAgICAgICBpMisrOwogICAgICAgIH0KICAgIH0KCiAgICB3aGlsZSAoaTEgPCBwYXJ0MS5zaXplKCkpIHsKICAgICAgICB0YWJbcG9jeiArIGkxICsgaTJdID0gcGFydDFbaTFdOwogICAgICAgIGkxKys7CiAgICB9CgogICAgd2hpbGUgKGkyIDwgcGFydDIuc2l6ZSgpKSB7CiAgICAgICAgdGFiW3BvY3ogKyBpMSArIGkyXSA9IHBhcnQyW2kyXTsKICAgICAgICBpMisrOwogICAgfQovKiAgICBmb3IoYXV0byBlIDogdGFiKXsKICAgIAljb3V0IDw8IGUgPDwgIiAiOwogICAgfQogICAgY291dCA8PCBlbmRsIDw8IGVuZGw7CiovCn0KCnZvaWQgc29ydG93YW5pZVByemV6U2NhbGFuaWUodmVjdG9yPGludD4mIHRhYiwgaW50IHBvY3osIGludCBrb24pIHsKICAgIC8vIHBvc29ydHVqIHRhYmxpY2UgdyBwcnplZHppYWxlIDxwb2N6IDoga29uPgogICAgCiAgICAvLyB3YXJ1bmVrIGJyemVnb3d5IC0+IHJvem1pYXIgMQogICAgaWYgKHBvY3ogPT0ga29uKSB7CiAgICAgICAgcmV0dXJuOwogICAgfQoKICAgIGludCBtaWQgPSAocG9jeiArIGtvbikgLyAyOwoKICAgIHNvcnRvd2FuaWVQcnplelNjYWxhbmllKHRhYiwgcG9jeiwgbWlkKTsKICAgIHNvcnRvd2FuaWVQcnplelNjYWxhbmllKHRhYiwgbWlkICsgMSwga29uKTsKCiAgICBzY2FsKHRhYiwgcG9jeiwga29uKTsKICAgIGZvcihhdXRvIGUgOiB0YWIpewogICAgCWNvdXQgPDwgZSA8PCAiICI7CiAgICB9CiAgICBjb3V0IDw8IGVuZGwgPDwgZW5kbDsKfQoKCmludCBtYWluKCkgewoJdmVjdG9yIDxpbnQ+IHRhYnsyLDEsNSw0LDN9OwoJc29ydG93YW5pZVByemV6U2NhbGFuaWUodGFiLCAwLCA0KTsKCWZvcihhdXRvIGVsZW0gOiB0YWIpewovLwkJY291dCA8PCBlbGVtIDw8ICIgIjsKCX0KCQoJcmV0dXJuIDA7Cn0=