Merge sort

It uses divide and conquer and use O(n) extra memory to achieve the O(nlogn) run time

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int l = 0, r = nums.size() -1;
        vector<int> temp(r-l+1);
        mergeSort(nums, temp, l, r);
        return nums;
    }

    void mergeSort(vector<int>& A, vector<int>& temp, int l, int r){
        if(l >= r)
            return;
        int m = (l+r)/2;
        mergeSort(A, temp, l, m);
        mergeSort(A, temp, m+1, r);
        merge(A, temp, l, m, r);
    }

    void merge(vector<int>& A, vector<int>& temp, int l, int m, int r){
        int p1 = l, p2 = m+1, p_temp = 0;
        while(p1 <= m && p2 <= r){
            if(A[p1] <= A[p2])
                temp[p_temp++] = A[p1++];
            else
                temp[p_temp++] = A[p2++];
        }
        while(p1 < m+1)
            temp[p_temp++] = A[p1++];
        while(p2 < r+1)
            temp[p_temp++] = A[p2++];
        for(int i = 0; i < r-l+1; i++){
            A[l+i] = temp[i];
        }
    }
};

The function MergeSort(nums, temp, start, end) will sort an array that starts at index start and whose last element is at index end.
So the subsequent subproblem will sort [start, middle], and [middle + 1, end].

Merge will mergetwo sorted subarrays A[l, m] and A[m + 1, r].

NOTICE, we uses index, not size in the while in merge that’s why we have p1 <= m.
If we use size, notice that an array that starts from index l and ends on index m will have size m – l + 1 and since p1 starts at l, it needs to go forward m steps to reach the last element.