C Program: Merge Sort

The insertion sort algorithm discussed in our previous tutorial uses an incremental approach to sort. Merge sort however uses the divide-and-conquer approach to sort numbers, which is recursive in nature.

Consider the below sequence of unsorted numbers:

( 6 -1 2 1 8 3 )

Here we will illustrate the use of Merge Sort to sort the above sequence in ascending order, which will result in the above set of numbers being sorted as follows.

( -1 1 2 3 6 8 )

The given $n$ sequence of numbers is divided into two subsequences of $\frac{n}{2}$ length each. These two subsequences are further sorted recursively using merge sort. They are then merged back into a single sequence.

The actual merging is perfomed inside the auxiliary merge() function which takes the parameters $A$, $p$, $q$ and $r$ where $A$ is the array containing the numbers and $p$, $q$ and $r$ are indices of array elements such that $p \le q \lt r$. The merge() function assumes that the two subarrays $A[p .. q]$ and $A[q + 1 .. r]$ are in sorted order and then merge them into a single sorted array replacing the original $A[p .. r]$ array.

The mergesort() function takes in the parameters $A$, $p$ and $r$, where is $A$ is the array of numbers to be sorted, and $p$ and $r$ are the indices of its first and last elements. As long as $p \lt r$, the algorithm goes on dividing the array into two equal subarrays with $A[p .. q]$ consisting of $\lceil \frac{n}{2} \rceil$ elements and $A[q+1 .. r]$ consisting of $\lfloor \frac{n}{2} \rfloor$ elements, recursively. When $p = r$, the divided subarray has only one element and the array is already sorted.

From here, the earlier merge() function is invoked to merge 1-item sequences into sorted sequences of length two. And next these two-item sequences are merged into sorted sequences of length four, and so on till the last two sequences of length $\frac{n}{2}$ are merged back to a single sorted array of original length $n$.

The C program below illustrates the merge sort algorithm we discussed above.

				
				#include <stdio.h>

				void merge(int A[], int p, int q, int r);
				void mergesort(int A[], int p, int r);


				int main() {
					int A[] = {6,-1,2,1,8,3}, n, i;

					// the size of given array
					n = 6;

					// merge sort
					mergesort(A, 0, n-1);

					// printing the sorted array
					for(i = 0; i < n; i++) {
						printf("%d ", A[i]);
					}

					return 0;
				}

				void merge (int A[], int p, int q, int r) {
					int n1 = q - p + 1;
					int n2 = r - q;
					int L[n1], R[n2];
					int i, j, k;

					for(i = 0; i < n1; i++) {
						L[i] = A[p+i];
					}

					for(j = 0; j < n2; j++) {
						R[j] = A[q+1+j];
					}

					i = 0;
					j = 0;
					k = p;

				  	while (i < n1 && j < n2) {
				        if (L[i] <= R[j]) {
				            A[k] = L[i];
				            i++;
				        }
				        else {
				            A[k] = R[j];
				            j++;
				        }
				        k++;
				    }
								  
				    while (i < n1) { 
				        A[k] = L[i]; 
				        i++; 
				        k++; 
				    } 

				    while (j < n2) { 
				        A[k] = R[j]; 
				        j++; 
				        k++; 
				    }
				}

				void mergesort (int A[], int p, int r) {
				    if (p < r) {
				        int q = (p+r)/2;
				        mergesort(A,p,q);
				        mergesort(A,q+1,r);
				        merge(A,p,q,r);
				    }
				}
				
			

On compiling and running the above C program, we get the sorted output as

				
					$ ./a.out
					-1 1 2 3 6 8
				
			

					
					#include <stdio.h>

					void merge(int A[], int p, int q, int r);
					void mergesort(int A[], int p, int r);

					int main() {
						int A[100], n, i;

						printf("Enter the dimension of the array: ");
						scanf("%d", &n);

						// array input
						for(i = 0; i < n; i++) {
							printf("Enter A[%d]: ", i);
							scanf("%d", &A[i]);
						}

						// merge sort
						mergesort(A, 0, n-1);

						// printing the sorted array
						for(i = 0; i < n; i++) {
							printf("%d ", A[i]);
						}

						return 0;
					}

					void merge (int A[], int p, int q, int r) {
						int n1 = q - p + 1;
						int n2 = r - q;
						int L[n1], R[n2];
						int i, j, k;

						for(i = 0; i < n1; i++) {
							L[i] = A[p+i];
						}

						for(j = 0; j < n2; j++) {
							R[j] = A[q+1+j];
						}

						i = 0;
						j = 0;
						k = p;

					  	while (i < n1 && j < n2) { 
					        if (L[i] <= R[j]) { 
					            A[k] = L[i]; 
					            i++; 
					        } 
					        else { 
					            A[k] = R[j]; 
					            j++; 
					        }       
					        k++; 
					    } 

					    while (i < n1) {
					        A[k] = L[i];
					        i++;
					        k++;
					    }

					    while (j < n2) {
					        A[k] = R[j];
					        j++;
					        k++;
					    }
					}

					void mergesort (int A[], int p, int r) {
					    if (p < r) {
					        int q = (p+r)/2;
					        mergesort(A,p,q);
					        mergesort(A,q+1,r);
					        merge(A,p,q,r);
					    }
					}