Merge Sort Program Example in C (New)

 Merge sort is a popular and efficient sorting algorithm that uses the divide-and-conquer approach to sort an array or a list of elements. The algorithm works by recursively dividing the array into smaller subarrays until they are single-element arrays. Then, it combines and sorts the subarrays to produce a sorted array.

The main steps of the Merge sort algorithm are as follows:

1. Divide the unsorted array into two halves, by finding the middle index.

2. Recursively sort the left half and the right half of the array.

3. Merge the two sorted halves by comparing the elements from both halves and placing them in the correct order.

The time complexity of the Merge sort algorithm is O(n log n), which makes it efficient for sorting large data sets. However, it requires additional space for merging the subarrays.

Merge sort is a stable sorting algorithm, which means that it maintains the relative order of equal elements in the sorted array. This property is useful in applications where maintaining the original order of equal elements is important.

Here's an example of a Merge Sort program in C:

#include 

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

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

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

    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;

        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    return 0;
}

The program first defines the `merge()` function that merges two sorted arrays, `mergeSort()` function that recursively divides the input array into two halves, and then sorts and merges them.

The main() function initializes an array with some values, prints the original array, calls mergeSort() to sort the array, and then prints the sorted array.