C Program to Implement Merge Sort

Introduction

Merge Sort is a classic divide-and-conquer sorting algorithm. It works by dividing the array into two halves, recursively sorting each half, and then merging the two sorted halves back together. The merge operation ensures that the final array is sorted. Merge Sort is known for its efficiency, particularly for large datasets, and has a time complexity of O(n log n).

Example:

• Input: Unsorted array [38, 27, 43, 3, 9, 82, 10]
• Output: Sorted array [3, 9, 10, 27, 38, 43, 82]

Problem Statement

Create a C program that:

• Implements the Merge Sort algorithm to sort an array.
• Takes an unsorted array as input and outputs the sorted array.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> for standard input-output functions.
2. Implement the Merge Function: This function merges two halves of an array in sorted order.
3. Implement the Merge Sort Function: This function recursively divides the array and merges the sorted halves.
4. Create a Main Function: Allow the user to input the array, apply merge sort, and display the sorted array.

C Program to Implement Merge Sort

#include <stdio.h>

// Function to merge two subarrays of arr[]
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;  // Size of the left subarray
    int n2 = right - mid;     // Size of the right subarray

    int L[n1], R[n2];  // Temporary arrays to hold the two halves

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

    // Merge the temporary arrays back into arr[left..right]
    int i = 0, j = 0, k = left;
    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 any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of R[], if 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) {
        int mid = left + (right - left) / 2;

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

        // Merge the sorted halves
        merge(arr, left, mid, right);
    }
}

int main() {
    int n;

    // Input the size of the array
    printf("Enter the number of elements in the array: ");
    scanf("%d", &n);

    int arr[n];

    // Input the elements of the array
    printf("Enter %d elements:\n", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // Apply Merge Sort
    mergeSort(arr, 0, n - 1);

    // Output the sorted array
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Function to Merge Two Subarrays

• The merge function merges two subarrays (L[] and R[]) back into the main array arr[].
• The subarrays are sorted during the merge process, ensuring that the combined array is sorted.
• The function handles leftover elements in either subarray after the main merging loop.

Function to Implement Merge Sort

• The mergeSort function is a recursive function that divides the array into two halves.
• It continues dividing the array until the base case is reached (i.e., a subarray with one element).
• The two halves are then merged back together in sorted order using the merge function.

Main Function

• The main function allows the user to input the size of the array and the elements.
• It then applies Merge Sort to the array and displays the sorted array.

Output Example

Example Output:

Enter the number of elements in the array: 7
Enter 7 elements:
38 27 43 3 9 82 10
Sorted array: 3 9 10 27 38 43 82

Example Output (Already Sorted):

Enter the number of elements in the array: 5
Enter 5 elements:
1 2 3 4 5
Sorted array: 1 2 3 4 5

Conclusion

This C program demonstrates how to implement Merge Sort, a stable and efficient sorting algorithm. Merge Sort is especially useful for sorting large datasets due to its time complexity of O(n log n). The program provides a clear example of how to apply the divide-and-conquer technique to sorting problems in C programming.