Skip to main content

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




Comments

Post a Comment

Popular posts from this blog

Creating a word Scramble game where you can drag and drop the word and create a complete word. (drag and drop word Scramble game).

Creating a word game using  phaser game engine which is a javascript based gaming engine  where u can drag and drop world like Word Scramble Game and complete a given word. your index.html file look like below < html > < head > < script src = "src/phaser.min.js" ></ script > < script src = "src/wordGame.js" ></ script > < script src = "src/main.js" ></ script > </ head > < body > </ body > </ html > 1.    <script src="src/phaser.min.js"></script> required to run the  phaser game engine. 2. rest of the two files deals with game logics      <script src="src/wordGame.js"></script>       <script src="src/main.js"></script> you can download whole project from https://github.com/manishchauhan/wordgame/tree/master just copy and paste the project in your local server and run ...
Post a Comment
Read more

starting with three.js and react with a very simple example

 1. three.js is undoubtedly the best library to create interactive content for the web in 3d. link https://threejs.org/ a working sample of three with react can be found below https://stackblitz.com/edit/react-7n5qf9?file=src%2FApp.js why choose threejs 1. lightweight  2.fast 3.big community  https://discourse.threejs.org/ 4. even you can use unity or unreal to publish html5 content but i don't think that would be acceptable in many cases. 5. open-source project. i created a running sample with React  https://stackblitz.com/edit/react-7n5qf9?file=src%2FApp.js
Post a Comment
Read more

A simple binary search tree with generic approach tree can store any type of data. (DFS and BFS)

 1. a binary search tree in c++ using a generic approach with both BFS and DFS approach    working tree    https://www.onlinegdb.com/edit/HkuQLdA-w code=> some properties of binary search tree-> 1. binary search tree is not always a balanced tree.  2. Inorder, traversing gives you sorted data.  3.  best is o(log n) and worst is O(n).  4. left node data is always less than root data and right node data always be greater than root data.  5. red-black tree STL map is a balanced binary search tree. *******************************************************************************/ #include <stdio.h> #include<iostream> #include<queue> using namespace std; template < typename T > class Node {   //can store any type of data private:   //genric data or store any type of data   T data;   //reference of left pointer   Node *left = nullptr;   //reference of right pointer   Node *rig...
Post a Comment
Read more