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[0]);

    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.