Merge Sort

This is another sorting technique having the same average-case and worst-case time complexities, but requiring an additional list of size n.
 
The technique that we use is the merging of the two sorted lists of size m and n to form a single sorted list of size (m + n). Given a list of size n to be sorted, instead of viewing it to be one single list of size n, we start by viewing it to be n lists each of size 1, and merge the first list with the second list to form a single sorted list of size 2.
 
Similarly, we merge the third and the fourth lists to form a second single sorted list of size 2, and so on. This completes one pass. We then consider the first sorted list of size 2 and the second sorted list of size 2, and merge them to form a single sorted list of size 4.
 
Similarly, we merge the third and the fourth sorted lists, each of size 2, to form the second single sorted list of size 4, and so on. This completes the second pass.
 
In the third pass, we merge these adjacent sorted lists, each of size 4, to form sorted lists of size 8. We continue this process until we finally obtain a single sorted list of size n as shown next.

To carry out this task, we require a function to merge the two sorted lists of size m and n to form a single sorted list of size (m + n). We also require a function to carry out one pass of the list to merge the adjacent sorted lists of the specified size. This is because we have to carry out repeated passes of the given list.
 
In the first pass, we merge the adjacent lists of size 1. In the second pass, we merge the adjacent lists of size 2, and so on. Therefore, we will call this function by varying the size of the lists to be merged.

Merge Sort with recursion

#include<stdio.h>
int arr[10]; // array to be sorted

int main()
{
	int n,i;

	printf("Enter the size of array\n"); // input the elements
	scanf("%d",&n);
	printf("Enter the elements:");
	for(i=0; i<n; i++)
		scanf("%d",&arr[i]);

	printf("before merge sort elements are :\n");
	for(i=0; i<n; i++)
		printf("%d ",arr[i]);
	printf("\n");

	printf("After merge sort elements are :\n");
	merge_sort(arr,0,n-1); // sort the array
	for(i=0; i<n; i++)
		printf("%d ",arr[i]);
	getchar();
	getchar();
	return 0;
}

int merge_sort(int arr[],int low,int high)
{
	int mid;
	if(low<high) {
		mid=(low+high)/2;
		// Divide and Conquer
		merge_sort(arr,low,mid);
		merge_sort(arr,mid+1,high);
		// Combine
		merge(arr,low,mid,high);
	}
}

int merge(int arr[],int l,int m,int h)
{
	int arr1[10],arr2[10]; 
	// Two temporary arrays to hold the two arrays to be merged
	int n1,n2,i,j,k;
	n1=m-l+1;
	n2=h-m;

	for(i=0; i<n1; i++)
		arr1[i]=arr[l+i];
	for(j=0; j<n2; j++)
		arr2[j]=arr[m+j+1];

	arr1[i]=9999; // To mark the end of each temporary array
	arr2[j]=9999;

	i=0;
	j=0;
	for(k=l; k<=h; k++) { //process of combining two sorted arrays
		if(arr1[i]<=arr2[j])
			arr[k]=arr1[i++];
		else
			arr[k]=arr2[j++];
	}
}

Merge Sort without recursion

#include<stdio.h>
#define MAX 10

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

	printf("Enter the number of elements, Max 10 : ");
	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;
			if (h2 >= n) // h2 exceeds the limlt of arr
				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++];
			l1 = h2 + 1;
		}

		for (i = l1; k < n; i++) //any pair left
			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]);
	}

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