Home » Data Structure

Merge Sort with and without Recursion using C program

In this article, we are going to learn about merge sort and implementing c program with and without using recursion.
Submitted by Manu Jemini, on January 24, 2018

Image source: https://www.ict.social/images/19/algorithms/sorting/merge-sort.png

Merge Sort is base on divide and conquer algorithm.

1) DIVIDING

In Merge Sort, we take a middle index and break the array into two sub-arrays. These sub-array will go on breaking till the array have only one element.

2) MERGING

When all we have is single elements we start merging the elements in the same order in which we have divided them. During Merging, we also sort the sub-arrays, because sorting 10 arrays of 2 elements is cheaper than sorting an array of 20 elements.

In the end, we will have an array of elements, which is sorted.

C program to implement Merge Sort using Recursion

#include<stdio.h>


void merge(array, low, mid, high )
{
	int temp[MAX];
	int i = low;
	int j = mid +1 ;
	int k = low ;

	while( (i <= mid) && (j <=high) )
	{
		if(array[i] <= array[j])
			temp[k++] = array[i++] ;
		else
			temp[k++] = array[j++] ;
	}/*End of while*/
	
	while( i <= mid )
		temp[k++]=array[i++];
	
	while( j <= high )
		temp[k++]=array[j++];

	for(i= low; i <= high ; i++)
		array[i]=temp[i];
	
}/*End of merge()*/

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 );
	}
}/*End of merge_sort*/

int main()
{
	int i,n;

	printf("Enter the number of elements : ");
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		printf("Enter element %d : ",i+1);
		scanf("%d",&array[i]);
	}

	printf("Unsorted list is :\n");
	for( i = 0 ; i<n ; i++)
		printf("%d ", array[i]);

	merge_sort( 0, n-1);

	printf("\nSorted list is :\n");
	for( i = 0 ; i<n ; i++)
		printf("%d ", array[i]);
	printf("\n");
	
	return 0;
}/*End of main()*/

C program to implement Merge Sort without using Recursion

#include <stdio.h>
#define MAX 30

int main()
{
	int arr[MAX],temp[MAX],i,j,k,n,size,l1,h1,l2,h2;

	printf("Enter the number of elements : ");
	scanf("%d",&n);

	for(i=0;i<n;i++)
	{
		printf("Enter element %d : ",i+1);
		scanf("%d",&arr[i]);
	}

	printf("Unsorted list is : ");
	for( i = 0 ; i<n ; i++)
		printf("%d ", arr[i]);

	/*l1 lower bound of first pair and so on*/
	for(size=1; size < n; size=size*2 )
	{
		l1=0;
		k=0;  /*Index for temp array*/
		while( l1+size < n)
		{
			h1=l1+size-1;
			l2=h1+1;
			h2=l2+size-1;
			/* h2 exceeds the limlt of arr */
			if( h2>=n ) 
				h2=n-1;
			
			/*Merge the two pairs with lower limits l1 and l2*/
			i=l1;
			j=l2;
			
			while(i<=h1 && j<=h2 )
			{
				if( arr[i] <= arr[j] )
					temp[k++]=arr[i++];
				else
					temp[k++]=arr[j++];
			}
			
			while(i<=h1)
				temp[k++]=arr[i++];
			while(j<=h2)
				temp[k++]=arr[j++];
			/**Merging completed**/
			/*Take the next two pairs for merging */
			l1=h2+1; 
		}/*End of while*/

		/*any pair left */
		for(i=l1; k<n; i++) 
			temp[k++]=arr[i];

		for(i=0;i<n;i++)
			arr[i]=temp[i];

		printf("\nSize=%d \nElements are : ",size);
		for( i = 0 ; i<n ; i++)
			printf("%d ", arr[i]);
		
	}/*End of for loop */
	
	printf("Sorted list is :\n");
	for( i = 0 ; i<n ; i++)
		printf("%d ", arr[i]);
	
	printf("\n");
	
	return 0;
}/*End of main()*/

Output