Merge Sort

mergesort.cpp

// Very simple mergesort implementation by cf/cebolinha
// Uses O(NlogN) memory, a bit more than the usual O(N)
#include <bits/stdc++.h>
using namespace std;

void merge_sort(vector<int> &v) {
  if (v.size() == 1) return;

  // Divide v into two vectors - Left and Right
  vector<int> L, R;
  for (int i = 0; i < v.size()/2; i++)
    L.push_back(v[i]);
  for (int i = v.size()/2; i < v.size(); i++)
    R.push_back(v[i]);

  // Sort subvectors
  merge_sort(L);
  merge_sort(R);

  // Merge the sorted vectors
  int Li = 0, Ri = 0;
  for (int i = 0; i < v.size(); i++) {
    if (Li == L.size()) v[i] = R[Ri++];
    else if (Ri == R.size()) v[i] = L[Li++];
    else if (L[Li] <= R[Ri]) v[i] = L[Li++];
    else v[i] = R[Ri++];
  }
}

int main() {
  // Read a vector
  int n; cin >> n;
  vector<int> v;
  for (int i = 0; i < n; i++) {
    int x; cin >> x;
    v.push_back(x);
  }

  merge_sort(v);

  // Output the vector
  for (auto x : v) cout << x << " ";
  cout << endl;
}