In this article I will explain or implement the merge sort algorithm in c programming language. In this I also give the output screen shoot of merge sort algorithm. Merge sort is based on the divide and conquer methodology. In divide and conquer methodology we divide the problem in sub problems and then solve the divided parts of problem and then combined the problem.
Merge sort provide the stability to sort the elements. Merge sort is also faster then the insertion sort because of the in insertion sort theta (n2) but the merge sort is theta(n lg n) because of the in merge sort running time is slowly increases then the insertion sort. But if the input is smaller then the insertion sort is faster then the merge sort.
Codding:-
#include <conio.h> #include <stdio.h> void mergeMethod(int [],int ,int,int); void merge_sortFunction(int [],int ,int); void main() { int i,lowVar,highVar,a[20],n; clrscr(); printf("enter the size of array for merge sort "); scanf("%d",&n); printf("enter the elements of array for merge sort"); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } lowVar=1; merge_sortFunction(a,low,n); printf("The sorted array is as "); for(i=1;i<=n;i++) { printf("%d",a[i]); } getch(); } void merge_sortFunction(int a[],int lowVar,int highVar) { int midVar; if(lowVar<highVar) { midVar=((lowVar highVar)/2); merge_sortFunction(a,lowVar,midVar); merge_sortFunction(a,midVar 1,highVar); mergeMethod(a,lowVar,midVar,highVar); } } void mergeMethod(int a[],int lowVar,int midVar,int highVar) { int i,j,b[20],h,k;h=lowVar; i=lowVar; j=midVar 1; while((h<=midVar) & (j<=highVar)) { if(a[h]<a[j]) { b[i]=a[h]; h=h+1; } else { b[i]=a[j]; j=j+1; } i=i+1; } if(h>midVar) { for(k=j;k<=highVar;k++) { b[i]=a[k]; i=i+1; } } else { for(k=h;k<=midVar;k++) { b[i]=a[k]; i=i+1; } } for(k=lowVar;k<=highVar;k++) { a[k]=b[k]; } }
Source Code:merge.zip
Output:-
Lets take the 10 size array which elements are 8, 4, 55, 2, 41, 4, 77, 8, 0, 25.
Then the output generate by this program is
output of merge sort algorithm in c programming language |