Merge sort algorithm in a classic way example contain c++ code using vector

Merge sort 

one of the highly used algorithm for sorting data


check out this video for more detail


https://www.youtube.com/watch?v=TzeBrDU-JaY


Benefits over other sorting algorithms for

•  faster than bubble sort, insertion sort and selection sort.
• always used when time complexity is your first priority over space complexity.
• when data is huge 1000+ records but space complexity is not a problem.
• huge unsorted data means lots of records is unsorted.
• don't use for small range where data is already sorted or only a few records needed to sort use selection sort in this case.
• take's O(n) space because its a divide a conquer algorithm.

running code just copy and paste and run it.

//

#include <iostream>

#include <vector>

#include <list>

using namespace std;

//@why merge sort

//faster than bubble sort

//faster than insertion sort

//KeyNote

//divide recursively array/vector into smaller parts until they are be reduced further

//merge recursively until you get the right result

//time complexity is O(nlogn)

//suitable for big range and if lots of item unsorted

//don't use for small range as merge sort required extra space which in liner O(n) its required two extra parts to hold the left and right part

void combine(vector<int> leftPart,vector<int> rightPart, vector<int> /*pass by reference because we want to manipulate same vector*/&myVector)

{

    //length of left part

    long L=leftPart.size();

    

    

    //length of right part

    long R=rightPart.size();

    

    

    //create three variables which would help us to fill the sorted items

    long LV=0;

    long RV=0;

    long FV=0;

    

    

    //check and fill the left and right part in sorted mannner

    while (LV<L && RV<R) {

        

        if(leftPart.at(LV)<=rightPart.at(RV))

        {

            myVector[FV]=leftPart.at(LV);

            LV+=1;

        }else

        {

            myVector[FV]=rightPart.at(RV);

            RV+=1;

        }

        FV+=1;

        

    }

    while (LV<L) {

        myVector[FV]=leftPart.at(LV);

        LV+=1;

        FV+=1;

    }

    while (RV<R) {

        myVector[FV]=rightPart.at(RV);

        RV+=1;

        FV+=1;

    }

}

void MergeSort(vector<int> &myVector)

{

    //get length of myVector if its less than 2 its can't sorted one element is always sorted.

    long myVectorLength=myVector.size();

    if(myVectorLength<2)

        return;

  

    //if length is greater than 1  we need divide vector into two parts

    //first part would be left part and second part would be right part

    

    //get middle of vector

    long mid=myVectorLength/2;

    

    //first part start from 0 to mid-1

    //and also we need a array which holds the first part

    vector<int> leftPart;

    //fill the left Part

    for(int i=0;i!=mid;i++)

    {

        leftPart.push_back(myVector[i]);

    }

    //deal with right part now

    //but it would start form mid

    vector<int> rightPart;

    

    for(long i=mid;i<myVector.size();i++)

    {

        rightPart.push_back(myVector[i]);

        

    }

    

    

    //recursively call this function until array is not broken to single item

    MergeSort(leftPart);

    MergeSort(rightPart);

    //combine array recursively

    combine(leftPart,rightPart,myVector);

    

};

int main(int argc, const char * argv[]) {

    //declare a vector which you needed to sort

    //step1 vector is unsorted

    vector<int> myVector={111,37,11,12,1,2,3,7,8,11,67,12,90};

    

    

    

    //step2

    //let check vector all records are unsorted

    for(auto var : myVector)

    {

        cout<<var<<endl;

    }

    

   

    //sort vector using vector

    MergeSort(myVector);

    

    cout<<"*****************";

    //let check vector all records are sorted

    for(auto var : myVector)

    {

        cout<<var<<endl;

    }

    

};

time complexity O(nlogn) in worst case.

 O(nlogn) in average and best case