Data Structures - Merge Sort

Basic programming - Merge Sort

Approach:

It is a Divide and Conquer problem. Divide the vector into small group to sort, and merge each small groups to the vector.

In the merge() function, we need two new vectors to store those element that is divided into two parts from the vector.
And, INT_MAX must be added at the end of leftvec and rightvec. It's a comparision use. E.g., all of elements in leftvec are smaller than rightvec, so do vec[i] = leftvec[left++] until leftvec[left] = INT_MAX, and afterwards do vec[i] = rightvec[right++]. Finally, those elements are sorted.

Time complexity:

Best Case：Ο(nlogn)

Worst Case：Ο(nlogn)

Average Case：Ο(nlogn)

Space complexity: O(n)

Stable/Unstable: Stable

Source code

Version 1

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

using namespace std;

void print(vector<int> vec){
    for(int i = 0; i < vec.size(); ++i){
        cout << vec[i] << " ";
    }
    cout << endl;
};

void merge(vector<int>& vec, int l, int mid, int r){
    vector<int> leftvec(vec.begin() + l, vec.begin() + mid + 1);
    vector<int> rightvec(vec.begin() + mid + 1, vec.begin() + r + 1);
    
    leftvec.insert(leftvec.end(), INT_MAX);
    rightvec.insert(rightvec.end(), INT_MAX);
    
    int left = 0, right = 0;
    
    for(int i = l; i <= r; ++i){
        if(leftvec[left] < rightvec[right]){
            vec[i] = leftvec[left];
            ++left;
        }else{
            vec[i] = rightvec[right];
            ++right;
        }
    }
    print(vec);
};

void mergeSort(vector<int>& vec, int l, int r){
    if(l < r){
        int mid = (l + r) / 2;
        mergeSort(vec, l, mid); // divide the leftside into subvector
        mergeSort(vec, mid + 1, r); // divdie the rightside into subvector
        merge(vec, l, mid, r); // conquer these elements in ascending order
    }
};

int main()
{
    vector<int> vec = {5,3,8,6,2,7,1,4};
    mergeSort(vec, 0, vec.size() - 1);
    
    cout << "Final answer:" << endl;
    print(vec);
    

    return 0;
}