DEV Community

Cover image for Merge Sort Implementation
bappasaha
bappasaha

Posted on

Merge Sort Implementation

[code in cpp](https://github.com/bappasahabapi/Algorithm.cpp/blob/master/Basic%20Data%20Structure-C%2B%2B/week-2/01-Merge-sort.cpp)**

[code in js]
(https://github.com/bappasahabapi/Algorithm.cpp/blob/master/Basic%20Data%20Structure-C%2B%2B/week-2/02-Merge-srot.js)

Merge Sort:divide and conquer algorithm

 01.First handle the base case;
 02. we have a loop which continues 0 to mid-1;
 03. Next divide the vector into two parts: vector b and vector c;
 04. Next we have sorted vector(means divide steps);
 05. Next the conquer steps
Enter fullscreen mode Exit fullscreen mode

Best Case : 

    [] --> []
    [a] --> [a]
Enter fullscreen mode Exit fullscreen mode

🎄 Implementation:

🔘 Divide part

🔥 It takes a vector input and return a vector output

       #include<bits/stdc++.h>
       using namespace std;
        vector<int> merge_sort(vector<int>a){

        }
Enter fullscreen mode Exit fullscreen mode

🔥 next define the base case inside the vector

if array size is 0 or 1 then return the array

        vector<int> merge_sort(vector<int>a)
        {
            if(a.size()<=1){
                return a;
            }
        }
Enter fullscreen mode Exit fullscreen mode

🔥 otherwise we divide the array at the midpoint

        vector<int> merge_sort(vector<int>a)
        {
            if(a.size()<=1){
                return a;
            }

            int mid =a.size()/2;
        }
Enter fullscreen mode Exit fullscreen mode

🔥 divide the vector into two parts

        vector<int> merge_sort(vector<int>a)
        {
            if(a.size()<=1){
                return a;
            }

            int mid =a.size()/2;

            // divide the vector into two parts
            vector<int>b;
            vector<int>c;
        }
Enter fullscreen mode Exit fullscreen mode

🔥 Divide the vector into two parts vector b and c where a=b+c

        vector<int> merge_sort(vector<int>a)
        {
            if(a.size()<=1){
                return a;
            }

            int mid =a.size()/2;

            vector<int>b;
            vector<int>c;
        }
Enter fullscreen mode Exit fullscreen mode

🔥 Divide the array into two parts if even then size of b = size of c otherwise

vector b starts with 0 to mid and vector c element start mid to i<a.size()

        vector<int> merge_sort(vector<int>a)
        {
            if(a.size()<=1){
                return a;
            }

            int mid =a.size()/2;

            vector<int>b;
            vector<int>c;

            for(int i=0;i<mid;i++)
                b.push_back(a[i]);

            for(int i=mid;i<a.size();i++)
                c.push_back(a[i]);
        }
Enter fullscreen mode Exit fullscreen mode

🔥 Next we call the two child array b and c

 here a get the sorted b elements
and a also get the sorted c elements
Enter fullscreen mode Exit fullscreen mode 
        vector<int> merge_sort(vector<int>a)
        {
            if(a.size()<=1){
                return a;
            }

            int mid =a.size()/2;

            vector<int>b;
            vector<int>c;

            for(int i=0;i<mid;i++)
                b.push_back(a[i]);

            for(int i=mid;i<a.size();i++)
                c.push_back(a[i]);

            //  now we get two sortd vector
            // This is divide steps
            vector<int>sorted_b=merge_sort(b);
            vector<int>sorted_c=merge_sort(c);


        }
Enter fullscreen mode Exit fullscreen mode

Conquer part

🔥 Store the two sorted array into vector a

        vector<int> merge_sort(vector<int>a)
        {
            if(a.size()<=1){
                return a;
            }

            int mid =a.size()/2;

            vector<int>b;
            vector<int>c;

            for(int i=0;i<mid;i++)
                b.push_back(a[i]);

            for(int i=mid;i<a.size();i++)
                c.push_back(a[i]);

            //  now we get two sortd vector
            // This is divide steps
            vector<int>sorted_b=merge_sort(b);
            vector<int>sorted_c=merge_sort(c);

            // return sorted array is stored in vector a
            vector<int> sorted_a;


        }
Enter fullscreen mode Exit fullscreen mode

🔥 Next we take two index and both are pointed in index 0

        vector<int> merge_sort(vector<int>a)
        {
            if(a.size()<=1){
                return a;
            }

            int mid =a.size()/2;

            vector<int>b;
            vector<int>c;

            for(int i=0;i<mid;i++)
                b.push_back(a[i]);

            for(int i=mid;i<a.size();i++)
                c.push_back(a[i]);

        //  now we get two sortd vector
        // This is divide steps
            vector<int>sorted_b=merge_sort(b);
            vector<int>sorted_c=merge_sort(c);

        // return sorted array is stored in vector a
            vector<int> sorted_a;

         // Next we take two index and both are pointed in index 0
            int idx1 =0;
            int idx2 =0;


        }
Enter fullscreen mode Exit fullscreen mode

🔥 next the loop will run the vector size of a ;

        vector<int> merge_sort(vector<int>a)
        {
            if(a.size()<=1){
                return a;
            }

            int mid =a.size()/2;

            vector<int>b;
            vector<int>c;

            for(int i=0;i<mid;i++)
                b.push_back(a[i]);

            for(int i=mid;i<a.size();i++)
                c.push_back(a[i]);

            //  now we get two sortd vector
            // This is divide steps
            vector<int>sorted_b=merge_sort(b);
            vector<int>sorted_c=merge_sort(c);

            // return sorted array is stored in vector a
            vector<int> sorted_a;

         // Next we take two index and both are pointed in index 0
            int idx1 =0;
            int idx2 =0;

    // next the loop will run the vector size of a;
            for(int i=0;i<a.size();i++)
            {
                if(sorted_b[idx1]<sorted_c[idx2])
                {
                    sorted_a.push_back(sorted_b[idx1]);
                    idx1++;
                }
                else
                {
                    sorted_a.push_back(sorted_c[idx2]);
                    idx2++;
                }
            }


        }
Enter fullscreen mode Exit fullscreen mode

🔥 Next check the corner case
That means we the index is reach the last element then we store the other array element .

🔥 next the loop will run the vector size of a ;

        #include<bits/stdc++.h>
        using namespace std;
        vector<int> merge_sort(vector<int>a)
        {
            if(a.size()<=1){
                return a;
            }

            int mid =a.size()/2;

            vector<int>b;
            vector<int>c;

            for(int i=0;i<mid;i++)
                b.push_back(a[i]);

            for(int i=mid;i<a.size();i++)
                c.push_back(a[i]);

            //  now we get two sortd vector
            // This is divide steps
            vector<int>sorted_b=merge_sort(b);
            vector<int>sorted_c=merge_sort(c);

            // return sorted array is stored in vector a
            vector<int> sorted_a;

         // Next we take two index and both are pointed in index 0
            int idx1 =0;
            int idx2 =0;

    // next the loop will run the vector size of a;
            for(int i=0;i<a.size();i++)
            {
                //corner case
                if(idx1==sorted_b.size())
                {
                            sorted_a.push_back(sorted_c[idx2]);
                            idx2++;
                }
                else if(idx2==sorted_c.size())
                {
                            sorted_a.push_back(sorted_b[idx1]);
                            idx1++;
                }


                if(sorted_b[idx1]<sorted_c[idx2])
                {
                    sorted_a.push_back(sorted_b[idx1]);
                    idx1++;
                }
                else
                {
                    sorted_a.push_back(sorted_c[idx2]);
                    idx2++;
                }
            }

            return sorted_a;

        }

        int main()
        {
            vector<int> a={5,3,7,1,8,9};
            vector<int>ans =merge_sort(a);
            for(int i=0;i<ans.size();i++)
                cout<<ans[i]<<" ";


            return 0;
        }
Enter fullscreen mode Exit fullscreen mode

Top comments (1)

Collapse
 
bappasahabapi profile image
bappasaha •

The whole code is here :

/*
complexity of merge sort : O(n*log n)
01.First handle the base case;

  1. we have a loop which continues 0 to mid-1;
  2. Next divide the vector into two parts: vector b and vector c;
  3. Next we have sorted vector(means divide steps);
  4. Next the conqure steps */ #include // #include // #include // #include using namespace std;

vectormerge_sort(vectorans)
{

//base case
if(ans.size()<=1)
    return ans;

// divide the vector into two parts
vector<int>Left;
vector<int>Right;

// we divide ans vector into two parts . here midPoint means where I divide the vector.
int midPoint =ans.size()/2;


// we have a loop which continues 0 to mid-1 porjonto to left e pathabo and mid theke n-1 size porjonto right e pathabo 
// left vage left gulo gelo , right e right gulo gelo

for(int i=0;i<midPoint;i++)
   Left.push_back(ans[i]);

for(int i=midPoint;i<ans.size();i++)
    Right.push_back(ans[i]);

// ekhon left half er jonno and right half er jonno ans ber korbo. eita bar korar jonno amra function takei call diye dibo
// now we get two sortd vector
// This is divide steps
vector<int>sorted_Left=merge_sort(Left);
vector<int>sorted_Right=merge_sort(Right);

//conqure steps: 
vector<int>sorted_ans;
int left_index=0;
int right_index=0;

for(int i=0; i<ans.size();i++)
{

    // check the corner case
    if(left_index==sorted_Left.size())
    {
        sorted_ans.push_back(sorted_Right[right_index]);
        right_index++;
    }
    else if(right_index==sorted_Right.size())
    {
        sorted_ans.push_back(sorted_Left[left_index]);
        left_index++;
    }
    //-----
        //todo: for acceding order
    else if(sorted_Left[left_index]<sorted_Right[right_index])
    {
        sorted_ans.push_back(sorted_Left[left_index]);
        left_index++;
    }
    //todo: for decending order
    // else if(sorted_Left[left_index]>sorted_Right[right_index])
    // {
    //     sorted_ans.push_back(sorted_Left[left_index]);
    //     left_index++;
    // }
    else
    {
        sorted_ans.push_back(sorted_Right[right_index]);
        right_index++;
    }

}
return sorted_ans;
Enter fullscreen mode Exit fullscreen mode

}

int main()
{
vector a={5,3,7,1,8,9};
vectorans =merge_sort(a);
for(int i=0;i<ans.size();i++)
cout<<ans[i]<<" ";

return 0;
Enter fullscreen mode Exit fullscreen mode

}

Read next

saumya27 profile image

Challenges And Best Practices In Mongodb Consulting: A Comprehensive Guide

Saumya -

adewalecodes profile image

Getting Started with NestJs: CRUD Operations

adewale-codes -

saumya27 profile image

Building Scalable Microservices With Node.Js: Frameworks And Features

Saumya -

fatimanawaz profile image

CentOS vs Ubuntu: A Tale of Two Linux Titans

fatimanawaz -