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.