class Solution
{
    public:
    void merge(int arr[], int l, int m, int r)
    {
         int n1=m-l+1; 
         int n2=r-m;
         // Initialization of temp arrays
         int L[n1],R[n2];
         // Initialization of first subarray
         for(int i=0;i<n1;i++)
         L[i]=arr[l+i];
         // Initialization of second subarray
         for(int j=0;j<n2;j++)
         R[j]=arr[m+1+j];
         int i=0,j=0,k=l;
         //Sorting the array using subarrays
         while(i<n1&&j<n2){
             if(L[i]<R[j]){
                 arr[k]=L[i];
                 i++;
             }
             else {
                 arr[k]=R[j];
                 j++;
             }
             k++;
         }
         //Remaining elements added to the array
         while(i<n1){
             arr[k]=L[i];
             i++;k++;
         }
         while(j<n2){
             arr[k]=R[j];
             j++;k++;
         }
    }
    public:
    void mergeSort(int arr[], int l, int r)
    {
        if(l>=r)
        return; //returns recursively
        int m=l+(r-l)/2;
        mergeSort(arr,l,m);
        mergeSort(arr,m+1,r);
        merge(arr,l,m,r);
    }
};