Envío 6756

Código

// Made by Daniel Diaz (@Danidiaztech)
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
#define forn(i, n) for (int i = 0; i < n; i++) // for in range in python
#define FOR(i, a, b) for (int i = a; i < b; i++) // for in range in python
#define int long long int
#define double long double
#define pb push_back
#define ff first
#define ss second
#define mk make_pair

typedef pair<int, int> pii;

const int MAX = 1e5 + 10;
const int MIN = -MAX;
const int INF = LLONG_MAX;
const int MINF = LLONG_MIN;
const int MOD = 1e9 + 7;

int a[MAX];

// p -> start, q -> middle,r -> end
void merge(int p, int q, int r){
  int n1 = q - p + 1;
  int n2 = r - q;

  int L[n1], M[n2];
  /// From start to middle
  for (int i = 0; i < n1; i++){
    L[i] = a[p + i];
  }

  // From middle to end
  for (int j = 0 ; j < n2; j++){
    M[j] = a[q + j + 1];
  }

  int i,j,k;
  i = j  = 0;
  k = p;

  while (i < n1 && j < n2){
    if (L[i] <=  M[j]){
      a[k]= L[i];
      i++;
    }
    else{
      a[k]= M[j];
      j++;
    }
    k++;
  }

  // Pick remaining elements and put them in the array
  while (i < n1){
    a[k] = L[i];
    i++;
    k++;
  }

  while (j < n2){
    a[k]= M[i];
    j++;
    k++;
  }
}

void mergesort(int l, int r){
  // Sort the array by halving it recursively
  // until we have parts of two elements, then, we sort these elements
  // and merge them again to form the sorted array
  if (l < r){
    int mid = l + (r - l) / 2;
    mergesort(l, mid);
    mergesort(mid + 1, r);

    // Merge the sorted arrays
    merge(l, mid, r);
  }
}

void quicksort(){

}

void heapsort(){

}

int32_t main() {
  fastInp;
  #if LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  #endif

  int n; cin >> n;
  forn(i, n) cin >> a[i];
  // heapsort();
  // quicksort();
  mergesort(0, n - 1);
  forn(i, n) cout << a[i] << " ";

  return 0;
}