[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
Best Case :
[] --> []
[a] --> [a]
🎄 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){
}
🔥 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;
}
}
🔥 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;
}
🔥 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;
}
🔥 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;
}
🔥 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]);
}
🔥 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
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);
}
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;
}
🔥 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;
}
🔥 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++;
}
}
}
🔥 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;
}
Top comments (1)
The whole code is here :
/*
complexity of merge sort : O(n*log n)
01.First handle the base case;
vectormerge_sort(vectorans)
{
}
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]<<" ";
}