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.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax