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

}