#include <iostream>
using namespace std;
void merge(int *arr, int lo, int m, int hi) {
int n1 = m - lo + 1; //maximo do subarray1
int n2 = hi - m; //maximo do subarray2
int *L = (int*)malloc(sizeof(int) * n1);
int *R = (int*)malloc(sizeof(int) * n2);
for (int i = lo; i < n1; i++) {
L[i] = arr[lo + i]; //cria array temporario para armazenar uma subarray
} //obs: vai de lo ateh n1-1
for (int j = hi; j < n2; j++) {
R[j] = arr[m + 1 + j]; //cria array temporario para armazenar outra subarray
}// obs vai de m+1 ateh n2-1
int i = 0;
int j = 0;
int k = lo; // comparar os subarrays e preencher o arr com os menores elementos de cada sub por vez
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i]; //se o de L for menor, arr recebe de L
i++;
} else {
arr[k] = R[j++]; //se o de R for menor, arr recebe de R
}
k++; //vai preenchendo arr[k]
}
while (i<n1){ // termina de preencher arr com o q falta de L
arr[k++] = L[i++];
}
while (j < n2) { // termina de preencher arr com o q falta de R
arr[k++] = R[j++];
}
}
void mergesort(int *arr, int lo, int hi) { //dividir e conquistar
if (lo < hi) {
int m = (hi + lo) / 2;
mergesort(arr, lo, m);
mergesort(arr, m + 1, hi);
merge(arr, lo, m, hi);
}
}
void printarr(int *arr, size_t size){ //imprime array ordenado
for (int i = 0; i < size; i++){
cout << arr[i] << " ";
}
}
int main() {
int N;
cin >> N;
int *vetor = (int *)malloc(sizeof(int) * N);
for (int i = 0; i < N; i++) {
cin >> vetor[i];
}
mergesort(vetor, 0, N);
printarr(vetor, N);
}
//https://pt.stackoverflow.com/q/189421/101
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwp2b2lkIG1lcmdlKGludCAqYXJyLCBpbnQgbG8sIGludCBtLCBpbnQgaGkpIHsKICAgIGludCBuMSA9IG0gLSBsbyArIDE7IC8vbWF4aW1vIGRvIHN1YmFycmF5MQogICAgaW50IG4yID0gaGkgLSBtOyAvL21heGltbyBkbyBzdWJhcnJheTIKICAgIGludCAqTCA9IChpbnQqKW1hbGxvYyhzaXplb2YoaW50KSAqIG4xKTsKICAgIGludCAqUiA9IChpbnQqKW1hbGxvYyhzaXplb2YoaW50KSAqIG4yKTsKICAgIGZvciAoaW50IGkgPSBsbzsgaSA8IG4xOyBpKyspIHsKICAgICAgICBMW2ldID0gYXJyW2xvICsgaV07IC8vY3JpYSBhcnJheSB0ZW1wb3JhcmlvIHBhcmEgYXJtYXplbmFyIHVtYSBzdWJhcnJheSAKICAgIH0gLy9vYnM6IHZhaSBkZSBsbyBhdGVoIG4xLTEKICAgIGZvciAoaW50IGogPSBoaTsgaiA8IG4yOyBqKyspIHsKICAgICAgICBSW2pdID0gYXJyW20gKyAxICsgal07IC8vY3JpYSBhcnJheSB0ZW1wb3JhcmlvIHBhcmEgYXJtYXplbmFyIG91dHJhIHN1YmFycmF5CiAgICB9Ly8gb2JzIHZhaSBkZSBtKzEgYXRlaCBuMi0xCiAgICBpbnQgaSA9IDA7CiAgICBpbnQgaiA9IDA7CiAgICBpbnQgayA9IGxvOyAvLyBjb21wYXJhciBvcyBzdWJhcnJheXMgZSBwcmVlbmNoZXIgbyBhcnIgY29tIG9zIG1lbm9yZXMgZWxlbWVudG9zIGRlIGNhZGEgc3ViIHBvciB2ZXoKICAgIHdoaWxlIChpIDwgbjEgJiYgaiA8IG4yKSB7CiAgICAgICAgaWYgKExbaV0gPD0gUltqXSkgewogICAgICAgICAgICBhcnJba10gPSBMW2ldOyAvL3NlIG8gZGUgTCBmb3IgbWVub3IsIGFyciByZWNlYmUgZGUgTAogICAgICAgICAgICBpKys7CiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgYXJyW2tdID0gUltqKytdOyAvL3NlIG8gZGUgUiBmb3IgbWVub3IsIGFyciByZWNlYmUgZGUgUgogICAgICAgIH0KICAgICAgICBrKys7IC8vdmFpIHByZWVuY2hlbmRvIGFycltrXQogICAgfQogICAgd2hpbGUgKGk8bjEpeyAvLyB0ZXJtaW5hIGRlIHByZWVuY2hlciBhcnIgY29tIG8gcSBmYWx0YSBkZSBMCiAgICAgICAgYXJyW2srK10gPSBMW2krK107CiAgICB9CiAgICB3aGlsZSAoaiA8IG4yKSB7IC8vIHRlcm1pbmEgZGUgcHJlZW5jaGVyIGFyciBjb20gbyBxIGZhbHRhIGRlIFIKICAgICAgICBhcnJbaysrXSA9IFJbaisrXTsKICAgIH0KfQp2b2lkIG1lcmdlc29ydChpbnQgKmFyciwgaW50IGxvLCBpbnQgaGkpIHsgLy9kaXZpZGlyIGUgY29ucXVpc3RhcgogICAgaWYgKGxvIDwgaGkpIHsKICAgICAgICBpbnQgbSA9IChoaSArIGxvKSAvIDI7CiAgICAgICAgbWVyZ2Vzb3J0KGFyciwgbG8sIG0pOwogICAgICAgIG1lcmdlc29ydChhcnIsIG0gKyAxLCBoaSk7CiAgICAgICAgbWVyZ2UoYXJyLCBsbywgbSwgaGkpOwogICAgfQp9CnZvaWQgcHJpbnRhcnIoaW50ICphcnIsIHNpemVfdCBzaXplKXsgLy9pbXByaW1lIGFycmF5IG9yZGVuYWRvCiAgICBmb3IgKGludCBpID0gMDsgaSA8IHNpemU7IGkrKyl7CiAgICAgICAgY291dCA8PCBhcnJbaV0gPDwgIiAiOwogICAgfQp9CmludCBtYWluKCkgewoJaW50IE47CgljaW4gPj4gTjsKCWludCAqdmV0b3IgPSAoaW50ICopbWFsbG9jKHNpemVvZihpbnQpICogTik7Cglmb3IgKGludCBpID0gMDsgaSA8IE47IGkrKykgewoJICAgIGNpbiA+PiB2ZXRvcltpXTsKCX0KCW1lcmdlc29ydCh2ZXRvciwgMCwgTik7CglwcmludGFycih2ZXRvciwgTik7Cn0KCi8vaHR0cHM6Ly9wdC5zdGFja292ZXJmbG93LmNvbS9xLzE4OTQyMS8xMDE=