Merge sort

mergeSort.cc

#include <vector>
#include <iostream>

using namespace std;

void merge_sort(vector<int>& arr);
void func(vector<int>& arr, int l, int r);
void merge(vector<int>& arr, int l, int m, int r);

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

void func(vector<int>& arr, int l, int r) {
  if (l >= r) return;
  const int mid = (l + r) >> 1;
  func(arr, l, mid);
  func(arr, mid + 1, r);
  merge(arr, l, mid, r);
}

void merge(vector<int>& arr, int l, int m, int r) {
  int i = l, j = m + 1, k = 0;
  vector<int> tmp(r - l + 1);
  while (i <= m && j <= r) {
    if (arr[i] < arr[j]) tmp[k++] = arr[i++];
    else tmp[k++] = arr[j++];
  }
  while (i <= m) tmp[k++] = arr[i++];
  while (j <= r) tmp[k++] = arr[j++];
  k = 0;
  for (i = l; i <= r; i++) arr[i] = tmp[k++];
}