Envío 1517

Código

#include <iostream>
#include <vector>

using namespace std;

void merge_sort(vector<int> &arr) {
  size_t size = arr.size();
  if (size > 1) {
    int middle = size / 2;
    vector<int> left_arr(middle);
    vector<int> right_arr(size - middle);

    for (int i = 0; i < middle; i++) {
      left_arr[i] = arr[i];
    }

    for (int i = 0; i + middle < size; i++) {
      right_arr[i] = arr[i + middle];
    }

    merge_sort(left_arr);
    merge_sort(right_arr);

    int l = 0;
    int r = 0;
    int i = 0;

    size_t left_arr_size = left_arr.size();
    size_t right_arr_size = right_arr.size();

    while (l < left_arr_size and r < right_arr_size) {
      if (left_arr[l] < right_arr[r]) {
        arr[i] = left_arr[l];
        l += 1;
      } else {
        arr[i] = right_arr[r];
        r += 1;
      }
      i += 1;
    }

    while (l < left_arr_size) {
      arr[i] = left_arr[l];
      l += 1;
      i += 1;
    }

    while (r < right_arr_size) {
      arr[i] = right_arr[r];
      r += 1;
      i += 1;
    }
  }
}

int main() {
  int n;
  cin >> n;
  vector<int> arr(n);
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  merge_sort(arr);
  for (int i = 0; i < arr.size(); i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
  return 0;
}