mergeSort.cpp

// Online C++ compiler to run C++ program online
#include <iostream>
#include <vector>
using namespace std;


void merge(vector<int>& arr, int start, int mid, int end) {

  int len1 = mid - start + 1;
  int len2 = end - mid;
    
  vector<int> left(len1);
  vector<int> right(len2);  

  for(int i = 0; i < len1; i++)
    left[i] = arr[start + i];  
  for(int j = 0; j < len2; j++)
    right[j] = arr[mid + 1 + j];

    
  int index1 = 0;   
  int index2 = 0; 
  int indexMerged = start;   

  while(index1 < len1 && index2 < len2) {
        
    if(left[index1] <= right[index2]) {
      arr[indexMerged] = left[index1];
      index1++;
    }
    else {    
      arr[indexMerged] = right[index2];
      index2++;
    }
    indexMerged++;
  } 
   
  while(index1 < len1) { 
    arr[indexMerged] = left[index1];
    index1++;
    indexMerged++;
  }

  while(index2 < len2) {
    arr[indexMerged] = right[index2];
    index2++;
    indexMerged++;  
  }
}

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

    mergeSort(arr, start, mid);
    mergeSort(arr, mid + 1, end);
    merge(arr, start, mid, end);
  }  
}


int main() {
 
  vector<int> arr {12, 11, 13, 5, 6, 7}; 
  
  mergeSort(arr, 0, arr.size() - 1);

  for(auto& a : arr) 
    cout << a << " ";

  return 0;  
}