# Merge Sort in C Language

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);

mergeSort(arr, 0, n - 1);

printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}
``````

The `merge` function takes an integer array `arr` and three integer values `l`, `m`, and `r`. It merges two sorted sub-arrays `arr[l..m]` and `arr[m+1..r]` into a single sorted sub-array `arr[l..r]`.

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

The `main` function creates an integer array and calls the `mergeSort` function to sort it. Finally, it prints the sorted array to the console.

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.