Merge_Sort.cpp

class Solution
{
    public:
    void merge(int arr[], int l, int m, int r)
    {
        int n1 = m-l+1;
        int n2 = r-m;
        
        int L[n1], R[n2];
        int k =l;
        
        for(int i=0; i<n1; i++){
            L[i] = arr[k++];
        }
        
        for(int i=0; i<n1; i++){
            R[i] = arr[k++];
        }
        
        int i =0;
        int j =0;
        k = l;
        
        while(i<n1 && j<n2){
            if(L[i]<= R[j]){
                arr[k++] = L[i++];
            }else{
                arr[k++] = R[j++];
            }
        }
        
        while(i<n1){
            arr[k++] = L[i++];
        }
        
        while(j<n2){
            arr[k++] = R[j++];
        }
        
        
    }
    public:
    void mergeSort(int arr[], int l, int r)
    {
        if(l>=r){
            return;
        }
        
        int m = l+ (r-l)/2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        
        merge(arr, l, m, r);
    }
};

GeeksForGeeks