Introduction

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

Program Structure

The merge sort program consists of the following main components:

• mergeSort: A function that recursively divides the array into halves.
• merge: A function that merges two sorted halves into a single sorted array.
• main: The entry point of the program where user input is handled and the sorting is initiated.

Code Implementation

#include 

// Function to merge two halves
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Create temporary arrays
    int L[n1], R[n2];

    // Copy data to temporary arrays
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    // Merge the temporary arrays back into arr[left..right]
    i = 0; // Initial index of first sub-array
    j = 0; // Initial index of second sub-array
    k = left; // Initial index of merged sub-array
    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++;
    }
}

// Function to implement merge sort
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        // Find the middle point
        int mid = left + (right - left) / 2;

        // Sort first and second halves
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // Merge the sorted halves
        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");
}

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

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

    mergeSort(arr, 0, arr_size - 1);

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

How It Works

1. The mergeSort function divides the array recursively until it has single elements.

2. The merge function then combines these single elements back into sorted order.

3. The sorted array is printed in the main function.

Conclusion

Merge sort is a powerful sorting algorithm that is particularly useful for large datasets and is easy to
implement in a recursive manner. It guarantees O(n log n) performance, making it a reliable choice
for many applications.