#include <chrono>
#include <iostream>
#include <vector>

using namespace std;

void merge(vector<int> &arr, int left, int mid, int right) {
  int n1 = mid - left + 1;
  int n2 = right - mid;

  vector<int> leftArr(n1);
  vector<int> rightArr(n2);

  for (int i = 0; i < n1; ++i) {
    leftArr[i] = arr[left + i];
  }
  for (int j = 0; j < n2; ++j) {
    rightArr[j] = arr[mid + 1 + j];
  }

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

  while (i < n1 && j < n2) {
    if (leftArr[i] <= rightArr[j]) {
      arr[k] = leftArr[i];
      ++i;
    } else {
      arr[k] = rightArr[j];
      ++j;
    }
    ++k;
  }

  while (i < n1) {
    arr[k] = leftArr[i];
    ++i;
    ++k;
  }

  while (j < n2) {
    arr[k] = rightArr[j];
    ++j;
    ++k;
  }
}

void mergeSort(vector<int> &arr, int left, int right) {
  if (left < right) {
    int mid = left + (right - left) / 2;

    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);

    merge(arr, left, mid, right);
  }
}

int main() {
  vector<int> array = {12, 11, 13, 5, 6, 7};

  auto start = chrono::high_resolution_clock::now();
  mergeSort(array, 0, array.size() - 1);
  auto end = chrono::high_resolution_clock::now();
  chrono::duration<double> elapsedTime = end - start;

  cout << "Sorted array: ";
  for (int num : array) {
    cout << num << " ";
  }
  cout << "\nTime taken: " << elapsedTime.count() << " seconds\n";

  return 0;
}