Merge Sort implementation in C

          Merge sort is one of the efficient sorting methods in data structures. It uses the divide and conquers method to sort the elements.

The logic is given below…

Logic:

The inputs are received from the user.

There are two functions. One is for divide the elements into two parts. Each part is sorted.

Finally, both are merged and displayed as output.

Here, is the code.

Code:

#include <stdio.h>

//merge sort function 1

void merge_process(int a[], int a_left, int a_mid, int a_right) {

    int i, j, k;

    int x1 = a_mid - a_left + 1;

    int x2 = a_right - a_mid;

    int L[x1], R[x2];

    for (i = 0; i < x1; i++) L[i] = a[a_left + i];

    for (j = 0; j < x2; j++) R[j] = a[a_mid + 1 + j];

    i = j = 0; k = a_left;

    while (i < x1 && j < x2)

        a[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];

    while (i < x1) a[k++] = L[i++];

    while (j < x2) a[k++] = R[j++];

}

//merge sort function 2

void merge_Sort(int a[], int a_left, int a_right) {

    if (a_left < a_right) {

        int a_mid = a_left + (a_right - a_left) / 2;

        merge_Sort(a, a_left, a_mid);

        merge_Sort(a, a_mid + 1, a_right);

        merge_process(a, a_left, a_mid, a_right);

    }

}

//main function

int main() {

    int arr[] = {21, 11, 5, 51, 76, 45};

    int n = sizeof(arr) / sizeof(arr[0]);

    merge_Sort(arr, 0, n - 1);

    for (int i = 0; i < n; i++) printf("%d ", arr[i]);

    return 0;

}

Output:

Compile and execute the above program in  C compiler to get the output.

5 11 21 45 51 76

Hope, this code is useful to you. The merge sort has time complexity of O(n logn).

Keep coding!!!