#include <iostream>
using namespace std;
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[l + i];
for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdm9pZCBtZXJnZShpbnQgYXJyW10sIGludCBsLCBpbnQgbSwgaW50IHIpIHsKICAgIGludCBuMSA9IG0gLSBsICsgMTsKICAgIGludCBuMiA9IHIgLSBtOwoKICAgIGludCBMW24xXSwgUltuMl07CiAgICBmb3IgKGludCBpID0gMDsgaSA8IG4xOyBpKyspIExbaV0gPSBhcnJbbCArIGldOwogICAgZm9yIChpbnQgaiA9IDA7IGogPCBuMjsgaisrKSBSW2pdID0gYXJyW20gKyAxICsgal07CgogICAgaW50IGkgPSAwLCBqID0gMCwgayA9IGw7CiAgICB3aGlsZSAoaSA8IG4xICYmIGogPCBuMikgewogICAgICAgIGlmIChMW2ldIDw9IFJbal0pIGFycltrKytdID0gTFtpKytdOwogICAgICAgIGVsc2UgYXJyW2srK10gPSBSW2orK107CiAgICB9CgogICAgd2hpbGUgKGkgPCBuMSkgYXJyW2srK10gPSBMW2krK107CiAgICB3aGlsZSAoaiA8IG4yKSBhcnJbaysrXSA9IFJbaisrXTsKfQoKdm9pZCBtZXJnZVNvcnQoaW50IGFycltdLCBpbnQgbCwgaW50IHIpIHsKICAgIGlmIChsIDwgcikgewogICAgICAgIGludCBtID0gbCArIChyIC0gbCkgLyAyOwogICAgICAgIG1lcmdlU29ydChhcnIsIGwsIG0pOwogICAgICAgIG1lcmdlU29ydChhcnIsIG0gKyAxLCByKTsKICAgICAgICBtZXJnZShhcnIsIGwsIG0sIHIpOwogICAgfQp9CgppbnQgbWFpbigpIHsKICAgIGludCBhcnJbXSA9IHszOCwgMjcsIDQzLCAzLCA5LCA4MiwgMTB9OwogICAgaW50IG4gPSBzaXplb2YoYXJyKSAvIHNpemVvZihhcnJbMF0pOwoKICAgIG1lcmdlU29ydChhcnIsIDAsIG4gLSAxKTsKCiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgICBjb3V0IDw8IGFycltpXSA8PCAiICI7CiAgICBjb3V0IDw8IGVuZGw7CgogICAgcmV0dXJuIDA7Cn0K