Envío 1955

Código

#include <iostream>
#include <vector>

using namespace std;

void merge(vector<int> &a, int left, int middle, int right) {
  // create temporal arrays
  int leftLength = middle - left + 1; 
  int rightLength = right - middle; 
  int arrLeft[leftLength];
  int arrRight[rightLength];
	 
  // fill temporal arrays
  for (int i = 0; i < leftLength; i++) {
	 arrLeft[i] = a[left + i]; 
  }
  for (int i = 0; i < rightLength; i++) {
	 arrRight[i] = a[middle + 1 + i]; 
  }

  // replace sorted values in original array 
  int l = 0, r = 0, o = left;
  // iterate over both array's
  while (l < leftLength and r < rightLength) {
	 if(arrLeft[l] <= arrRight[r]) {
		a[o++] = arrLeft[l++];
	 } else {
		a[o++] = arrRight[r++];
	 }
  }
  // if there are items left in either temp array, transfer them
  while (l<leftLength) {
	 a[o++] = arrLeft[l++];
  }
  while (r<rightLength) {
	 a[o++] = arrRight[r++];
  }
}

void do_merge_sort(vector<int> &a, int left, int right) {
  if (left < right) {
	 int middle = left + (right - left)/2;
	 do_merge_sort(a, left, middle);
	 do_merge_sort(a, middle + 1, right);
	 merge(a, left, middle, right);
  }
}

void merge_sort(vector<int> &a) {
  do_merge_sort(a, 0, a.size()-1);
}

void print(const vector<int> &a) {
  for (int i = 0; i < a.size(); i++) {
    cout << a[i] << " ";
  }
  cout << endl;
}

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }
  merge_sort(a);
  print(a);
  return 0;
}