Merge Sort

Given an array arr[], its starting position l and its ending position r. Sort the array using merge sort algorithm.

• Time : O(nlogn)
• Space : O(n)

class Solution {
public:
    void merge(int arr[], int l, int m, int r) {
        int left = l, right = m + 1;
        vector<int> sorted;
        while(left <= m and right <= r) {
            if(arr[left] < arr[right]) sorted.push_back(arr[left++]);
            else sorted.push_back(arr[right++]);
        }
        while(left <= m) sorted.push_back(arr[left++]);
        while(right <= r) sorted.push_back(arr[right++]);
        for(int i = l; i <= r; i++)
            arr[i] = sorted[i - l];
    }

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);
    }
};