# Merge Sort

Algorithm Video:

Merge Sort Combines Two Sorted file in a large bigger sorted files:
This Merge sort happens in a two steps:

This sorting is a example of divide and conquer approach:
1. Selection: Splits a list into two lists (This process is recursive approach)
2. Merging: It joins two list in a one list (It follows the pesudocode in itertive manner)

Pseudocode:

```void Merges(int *A,int *left,int *right,int nR)
{
nL=length of(L) //lenght of left
nR=length of(R) //length of right

i=0,j=0,k=0;

while(i<nL && j<nR)
{
if(left[i]<=right[j])
{
A[k]=left[i];
i=i+1;
}
else
{
A[k]=right[j];
j=j+1;
}
k=k+1;
}
while(i<nL)
{
A[k]=left[i];
k=k+1;
i=i+1;
}
while(j<nR)
{
A[k]=right[j];
j=j+1;
k=k+1;
}
}

void MergeSort(A)
{

n=length of(A)
if(n<2) return;
int mid;

mid=n/2;

L=array of size(mid); //left
R=array of size(n-mid); //right

for(int i=0; i<mid; i++)
{
L[i]=A[i];
}
for(int i=mid; i<n; i++)
{
R[i-mid]=A[i];
}

MergeSort(L);
MergeSort(R);
Merges(A,L,R);
}```

Implementation:
code with extra malloc declaration:

```#include<bits/stdc++.h>
using namespace std;

void Merges(int *A,int *left,int nL,int *right,int nR)
{
//int nL=sizeof(left)/sizeof(left[0]);
//int nR=sizeof(right)/sizeof(right[0]);
//cout<<nR<<" ";
int i,j,k;
i=0,j=0,k=0;

while(i<nL && j<nR)
{
if(left[i]<=right[j])
{
A[k++]=left[i++];
//i++;
}
else
{
A[k++]=right[j++];
//  j++;
}
//k++;
}
while(i<nL)
{
A[k++]=left[i++];
//k++;
//i++;
}
while(j<nR)
{
A[k++]=right[j++];
//j++;
//k++;
}
}

void MergeSort(int *A,int n)
{
if(n<2) return;
int mid,*L,*R;

mid=n/2;

L=(int*)malloc(mid*sizeof(int));
R=(int*)malloc((n-mid)*sizeof(int));
//int left[mid];
//int right[n-mid];
// int lefts=sizeof(left)/sizeof(left[0]);
//cout<<lefts<<" size";
for(int i=0; i<mid; i++)
{
L[i]=A[i];
}
for(int i=mid; i<n; i++)
{
R[i-mid]=A[i];
}

MergeSort(L,mid);
MergeSort(R,n-mid);
Merges(A,L,mid,R,n-mid);
free(L);
free(R);
}

int main()
{
int A[]= {2,4,1,6,8,5,3,7};
int sizes=sizeof(A)/sizeof(A[0]);
//Merges(A,0,8);
MergeSort(A,sizes);
for(int i=0; i<sizes; i++)
{
cout<<A[i]<<" ";
}
return 0;
}
```

code by me without  extra malloc:

```#include<bits/stdc++.h>
using namespace std;

void Merges(int *A,int *left,int nL,int *right,int nR)
{
//int nL=sizeof(left)/sizeof(left[0]); //i am not using this explained in this link

int i,j,k;
i=0,j=0,k=0;

while(i<nL && j<nR)
{
if(left[i]<=right[j])
{
A[k++]=left[i++];
}
else
{
A[k++]=right[j++];

}

}
while(i<nL)
{
A[k++]=left[i++];
}
while(j<nR)
{
A[k++]=right[j++];
}
}

void MergeSort(int *A,int n)
{
if(n<2) return;
int mid;

mid=n/2;

int L[mid];
int R[n-mid];

for(int i=0; i<mid; i++)
{
L[i]=A[i];
}
for(int i=mid; i<n; i++)
{
R[i-mid]=A[i];
}

MergeSort(L,mid);
MergeSort(R,n-mid);
Merges(A,L,mid,R,n-mid);
}

int main()
{
int A[]= {2,4,1,6,8,5,3,7};
int sizes=sizeof(A)/sizeof(A[0]);
//Merges(A,0,8);
MergeSort(A,sizes);
for(int i=0; i<sizes; i++)
{
cout<<A[i]<<" ";
}
return 0;
}
```

output:

`1 2 3 4 5 6 7 8`

Analysis of Running Time Complexity:

Worst case, Best case, Avergae case: Theta(nlogn)
Space Complexity: Theta(n)

This link can help to solve problems:
https://gist.github.com/mycodeschool/9678029
https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/tutorial/

http://www.sanfoundry.com/cpp-program-implement-merge-sort/

It would be a great help, if you support by sharing :)
Author: zakilive