DAA - 6.Merge sort (BCA-IV sem lab KSWU)

 

 6. Program to sort N Numbers using MERGE SORT 

ALGORITHM : 

Step 1 : Declare left and right var which will mark the extreme indices of the array

Step 2: Left will be assigned to 0 and right will be assigned to n-1

Step 3: Find mid = (left+right)/2

Step 4: Call mergeSort on (left,mid) and (mid+1,rear)

MergeSort(arr, left, right):

    if left > right 

        return

    mid = (left+right)/2

    mergeSort(arr, left, mid)

    mergeSort(arr, mid+1, right)

    merge(arr, left, mid, right)

end

Step 5: continue till left<right

Step 6: merge on the 2 sub problem

 

SOURCE CODE :

/*Mergesort*/ 

#include<stdio.h>

#include<conio.h>

#include <time.h>

int a[50];

void merge(int,int,int);

void merge_sort(int low,int high)

{

int mid;

if(low<high)

{

 mid=(low+high)/2;

 merge_sort(low,mid);

merge_sort(mid+1,high);

 merge(low,mid,high);

}

}

void merge(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];

}

int main()

{

int num,i;

clock_t start, end;

double cpu_time_used;

start = clock();

clrscr();

printf("\n\t\t\tMERGE SORT\n");

printf("\nEnter the Size of the Array: ");

scanf("\n%d",&num);

printf("\nEnter %d numbers: \n",num);

for(i=1;i<=num;i++)

{

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

}

merge_sort(1,num);

printf("\nSORTED ORDER USING MERGESORT ARE:");

for(i=1;i<=num;i++) printf("\n %d",a[i]);

end = clock();

     cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;

printf("\n The time taken for execution is %f seconds", cpu_time_used);

getch();

}

OUTPUT 1:

OUTPUT 2 :