Data Structures Merge Sort C Program

Data Structures Lab Manual / Merge Sort C Program

Program Name: Write a C Program for Merge Sort in Data Structures

Theory

Merge sort uses the divide and conquer approach to sort the elements. Merge sort 
repeatedly breaks down a array into several sub- arrays until each array consists 
of a single element and merging those sub- arrays in a manner that results into 
a sorted array.

Program Code

#include <stdio.h>  
 
void merge(int a[], int beg, int mid, int end)    
{    
int i, j, k;  
int n1 = mid - beg + 1;    
int n2 = end - mid;          
int LeftArray[n1], RightArray[n2]; //temporary arrays  
      
// copying data to temp arrays 
for (int i = 0; i < n1; i++)    
LeftArray[i] = a[beg + i];    

for (int j = 0; j < n2; j++)    
RightArray[j] = a[mid + 1 + j];    
      
i = 0; 
j = 0;   
k = beg;  
      
while (i < n1 && j < n2)    
{    
if(LeftArray[i] <= RightArray[j])    
{    
a[k] = LeftArray[i];    
i++;    
}    

else    
{    
a[k] = RightArray[j];    
j++;    
}    

k++;    
} 
   

while (i<n1)    
{    
a[k] = LeftArray[i];    
i++;    
k++;    
}    
      
while (j<n2)    
{    
a[k] = RightArray[j];    
j++;    
k++;    
}    
}    
  
void mergeSort(int a[], int beg, int end)  
{  
if (beg < end)   
{  
int mid = (beg + end) / 2;  
mergeSort(a, beg, mid);  
mergeSort(a, mid + 1, end);  
merge(a, beg, mid, end);  
}  
}  
  
 
int main()  
{  
int i, n, a[20];  

printf("Merge Sort\n"); 
printf("Enter Number 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("Merge Sorted Array Elements List: ");  

for (i = 0; i < n; i++)  
printf("%d\t ", a[i]); 
}

Input:
Merge Sort
Enter Number of Elements: 5
Enter Array Elements: 5 2 9 7 1

Output:
Merge Sorted Array Elements List: 1	 2	 5	 7	 9

Home Back