**Merge sort** is a *popular divide-and-conquer sorting algorithm* that recursively divides the input array into two halves, sorts each half, and then merges the sorted halves back together. In C language, an implementation of the **Merge Sort algorithm** can be as follows:

```
#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[n1], R[n2];
/* copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++) {
L[i] = arr[l + i];
}
for (j = 0; j < n2; j++) {
R[j] = arr[m + 1 + j];
}
/* merge the temp arrays back into arr[l..r] */
i = 0; /* initial index of first subarray */
j = 0; /* initial index of second subarray */
k = l; /* initial index of merged subarray */
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
/* copy the remaining elements of L[], if there are any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* copy the remaining elements of R[], if there are any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2; // middle index
/* sort first and second halves */
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
/* merge the sorted halves */
merge(arr, l, m, r);
}
}
int main() {
int arr[] = { 12, 11, 13, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```

The

function takes an integer array **merge**`arr`

and three integer values

, **l**

, and **m**

. It merges two sorted sub-arrays **r**

and **arr[l..m]**** arr[m+1..r] **into a single sorted sub-array

**arr[l..r]**

.The

function recursively sorts the array by dividing it into two halves, sorting each half, and then merging them back together using the **mergeSort**

function.**merge**

The

function creates an integer array and calls the **main**

function to sort it. Finally, it prints the sorted array to the console.**mergeSort**

Note that the *worst-case time complexity of merge sort is O(n log n)*, which makes it very efficient for sorting large arrays. However, it has a higher overhead than other algorithms like insertion sort or selection sort for small arrays.