DS || Section B || Pgm 2 || Program to sort the given list using merge sort technique.

 #include<stdio.h>

void merge(int a[],int i1,int j1,int i2,int j2)

{

int temp[50]; //array used for merging

int beg1,beg2,k;

beg1=i1; //beginning of the first list

beg2=i2; //beginning of the second list

k=0;

while(beg1<=j1 && beg2<=j2) //while elements in both lists

{

if(a[beg1]<a[beg2])

temp[k++]=a[beg1++];

else

temp[k++]=a[beg2++];

}

while(beg1<=j1) //copy remaining elements of the first list

temp[k++]=a[beg1++];

while(beg2<=j2) //copy remaining elements of the second list

temp[k++]=a[beg2++];

//Transfer elements from temp[] back to a[]

for(beg1=i1,beg2=0;beg1<=j2;beg1++,beg2++)

a[beg1]=temp[beg2];

}

void mergesort(int a[],int i,int j)

{

int mid;

if(i<j)

{

mid=(i+j)/2;

mergesort(a,i,mid); //left recursion

mergesort(a,mid+1,j); //right recursion

merge(a,i,mid,mid+1,j); //merging of two sorted sub-arrays

}

}

void main()

{

int a[10],n,i;

printf("Enter no of elements:");

scanf("%d",&n);

printf("Enter array elements:");

for(i=0;i<n;i++)

scanf("%d",&a[i]);

mergesort(a,0,n-1);

printf("\nSorted array is :\n");

for(i=0;i<n;i++)

printf("%d \n",a[i]);

}