# 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