• Merging is process of combining two sorted files into a third sorted file
• Given two sorted arrays A and B each of size k/2, merge them into an array C of size k. Array C should also be sorted
• Here we are going to merge two pre-sorted arrays

Time Complexity

• Recurrence relation
• T(n)=2T(n/2)+n
• What will be solution?

C++ code for merge sort

#include<iostream>
#include<conio.h>
#include<cstdlib>
#include<time.h>

using namespace std;

void merge(int a[],int low,int mid,int high)
{
int h,i,j,b[50],k;
h=low;
i=low;
j=mid+1;

while(h<=mid&&j<=high)
{
if(a[h]<=a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
for(k=low;k<=high;k++) a[k]=b[k];
}

void merge_sort(int a[],int left, int right)
{
if(left-right!=0)
{
int mid=(left+right)/2;
merge_sort(a,left,mid);
merge_sort(a,mid+1,right);
merge(a,left,mid,right);
}
}

int main()
{
srand(time(0));
int a[10];

for(int i=0;i<=9;i++)
a[i]=rand()%100;
for(int i=0;i<=9;i++)
cout<<a[i]<<” “;
cout<<endl;
merge_sort(a,0,9);
for(int i=0;i<=9;i++)
cout<<a[i]<<” “;

getch();
}

Merge sort analysis 

void MergeSort(int A[],int lower,int upper)

{

if (lower==upper)

return;

int middle=(lower+upper)/2;

MergeSort(A,lower,middle);

MergeSort(A,middle+1,upper);

MergeArray(A,lower,middle,middle+1,upper);

}

void MergeArray(int A[],int lower1,int upper1,int lower2,int upper2)

{

int size=(upper1-lower1+1) + (upper2-lower2+1);

int i,j,k,*C=new int[size];

for(i=0,j=lower1,k=lower2;j<=upper1 && k<=upper2;i++)

if(A[j]<=A[k])  C[i]=A[j++];

else C[i]=A[k++];

while(j<=upper1)  C[i++]=A[j++];

while(k<=upper2)  C[i++]=A[k++];

j=(lower1<lower2)?lower1:lower2;

for(i=0;i<size;i++,j++)

A[j]=C[i];

}