C Program to Implement Merge Sort

1. Introduction

Merge Sort is a divide-and-conquer algorithm that works by recursively splitting an array into two halves, sorting each half, and then merging the two sorted halves back together. It guarantees a time complexity of O(n log n), making it efficient for larger datasets.

2. Program Overview

In this program, we will:

1. Implement the merge function that merges two sorted halves of an array.

2. Implement the mergeSort function that recursively splits and sorts the array.

3. Sort an array of integers using Merge Sort.

4. Display the sorted array.

3. Code Program

#include <stdio.h>

// Merges two subarrays of arr[].
void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    // create temporary 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;
    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++;
    }

    // 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++;
    }
}

// Recursive function that sorts the array
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2; // Find the middle point

        mergeSort(arr, l, m);   // Sort first half
        mergeSort(arr, m + 1, r); // Sort second half

        merge(arr, l, m, r); // Merge the sorted halves
    }
}

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

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

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

    mergeSort(arr, 0, n - 1);

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

    return 0;
}

Output:

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

4. Step By Step Explanation

1. The merge function is responsible for merging two sorted halves of an array. We copy the elements of the two halves into two temporary arrays L[] and R[]. We then iterate through L[] and R[], copying the smaller element of the two back into the original array.

2. The mergeSort function is a recursive function that splits the array into two halves, sorts each half by recursively calling itself, and then merges the two sorted halves using the merge function.

3. The printArray function is a utility function to display the elements of an array.

4. The main function initializes an array, prints it, sorts it using merge sort, and then prints the sorted array.

Merge Sort is particularly efficient for larger datasets and is used in many high-performance applications because of its predictable O(n log n) time complexity.