text: #include <iostream>
  
  using namespace std;
  
  template <class T>
  void merge(T* arr, int l, int m, int r){
      int i, j, k;
      int n1 = m - l + 1;
      int n2 =  r - m;
  
      /* create temp arrays */
      T* L = new T[n1];
      T* R = new T[n2];
      //T L[n1], R[n2];
  
      /* Copy data to temp arrays L[] and R[] */
      for (i = 0; i < n1; i++)
          L[i] = arr[l + i];
      for (j = 0; j < n2; j++)
          R[j] = arr[m + 1+ j];
  
      /* Merge the temp arrays back into arr[l..r]*/
      i = 0; // Initial index of first subarray
      j = 0; // Initial index of second subarray
      k = l; // Initial index of merged subarray
      while (i < n1 && j < n2)
      {
          if (L[i] <= R[j])
          {
              arr[k] = L[i];
              i++;
          }
          else
          {
              arr[k] = R[j];
              j++;
          }
          k++;
      }
  
      /* Copy the remaining elements of L[], if there
         are any */
      while (i < n1)
      {
          arr[k] = L[i];
          i++;
          k++;
      }
  
      /* Copy the remaining elements of R[], if there
         are any */
      while (j < n2)
      {
          arr[k] = R[j];
          j++;
          k++;
      }
  
      delete[] L;
      delete[] R;
  
  }
  
  template <class T>
  void mergesort(T* array, int left, int right){
      if (left < right)
      {
          // Same as (l+r)/2, but avoids overflow for
          // large l and h
          int middle = left+(right-left)/2;
  
          // Sort first and second halves
          mergesort(array, left, middle);
          mergesort(array, middle+1, right);
  
          merge(array, left, middle, right);
      }
  }
  