MergeSort.cpp

# include<iostream>
# include<vector>

using namespace std;


// O(nlogn)
void MergeSort(vector<int>& arr,int size){
    vector<int> res=arr;
    for(int seg=1;seg<size;seg+=seg){
        for(int i=0;i<size;i+=seg+seg){
            int low=i;
            int k=low;
            int high=(min)(i+seg+seg,size);
            int mid = (min)(i+seg,size);
            int start1= low, end1 = mid;
            int start2= mid, end2 = high;
            while(start1<end1 && start2<end2){
                res[k++]=arr[start1]<arr[start2]? arr[start1++]:arr[start2++];
            }
            while(start1<end1) res[k++]=arr[start1++];
            while(start2<end2) res[k++]=arr[start2++];
        }
        arr=res;
    }
}


int main(){
    vector<int> arr={1,2,110,2,40,482,93,40,2,20,59,99};
    MergeSort(arr,arr.size());
    for(int i=0;i<arr.size();i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}