Merge Sort

Textbook

Description:

Example:

Note

Idea:

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

Code:

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

void merge(vector<int> & nums, int left, int mid, int right){
    int n1=mid - left + 1;
    int n2=right - mid;

    vector<int> left_nums(nums.begin()+left, nums.begin()+mid+1);
    vector<int> right_nums(nums.begin()+mid+1, nums.begin()+right+1);

    int i=0, j=0;
    int icurr=left;

    while(i<n1 && j<n2){
        if(left_nums[i]<=right_nums[j]){
            nums[icurr++]=left_nums[i++];
        }
        else{
            nums[icurr++]=right_nums[j++];
        }
    }
    if(i!=n1){
        while(i<n1){
            nums[icurr++]=left_nums[i++];
        }
    }
    else{
        while(j<n2){
            nums[icurr++]=right_nums[j++];
        }
    }
}

void mergeSort(vector<int> & nums, int left, int right){
    if(left < right){
        int mid = left + (right-left)/2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid+1, right);
        merge(nums, left, mid, right);
    }
}

void mergeSort(vector<int> & nums){
    mergeSort(nums, 0, nums.size()-1);
}

int main(){
    vector<int> input={3,4,2,5,6,7,2,3,3,8,9,23,43,22,1,23};

    for(auto e: input){
        cout<<e<<' ';
    } cout<<'\n';

    mergeSort(input);

    for(auto e: input){
        cout<<e<<' ';
    } cout<<'\n';

}