How to Sort an Array using Merge Sort in C

To sort an array using Merge Sort in C, we use the divide-and-conquer approach, where the array is recursively divided into two halves until each half contains a single element, and then these halves are merged back in a sorted order.

Understanding Merge Sort Algorithm

Merge Sort is an efficient sorting algorithm with a time complexity of O(n log n). It works as follows:

Divide the array into two halves.
Recursively sort both halves.
Merge the sorted halves back together.

Examples of Merge Sort in C

1. Sorting an Array Using Merge Sort

In this example, we implement the Merge Sort algorithm in C to sort an array of integers in ascending order.

main.c

</>

Copy

#include <stdio.h>

// Function to merge two halves of the array
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    int leftArr[n1], rightArr[n2];

    for (int i = 0; i < n1; i++)
        leftArr[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        rightArr[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

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

    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

// Recursive function to perform Merge Sort
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

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

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Original array:\n");
    printArray(arr, size);

    mergeSort(arr, 0, size - 1);

    printf("Sorted array:\n");
    printArray(arr, size);

    return 0;
}

Explanation:

We define the function merge() to merge two sorted halves of the array.
The function mergeSort() recursively divides the array into two halves until each contains one element.
After recursion, the merge() function combines the sorted halves into a single sorted array.
The printArray() function is used to display the original and sorted arrays.
The main() function initializes an array, prints it, calls mergeSort(), and then prints the sorted array.

Output:

Original array:
38 27 43 3 9 82 10 
Sorted array:
3 9 10 27 38 43 82

Conclusion

In this tutorial, we implemented Merge Sort in C and covered:

Understanding the divide-and-conquer approach of Merge Sort.
Writing a program to sort an array using Merge Sort.
Breaking the array into smaller parts and merging them in sorted order.

Merge Sort is one of the most efficient sorting algorithms, especially for large datasets, and guarantees a stable sorting order.

TutorialKart

How to Sort an Array using Merge Sort in C