C Program For Merge Sort Algorithm In Data Structure

Sorting is a fundamental operation in computer science, crucial for organizing data efficiently. Merge Sort stands out as an efficient, comparison-based sorting algorithm, known for its stability and guaranteed performance. In this article, you will learn how to implement the Merge Sort algorithm in C, understanding its underlying principles and practical application.

Problem Statement

Efficiently arranging a collection of elements in a specific order (ascending or descending) is a common challenge in data processing. An unsorted array of numbers, for instance, makes searching for specific values or performing range queries highly inefficient. For large datasets, a naive sorting approach can lead to prohibitive execution times, demanding an algorithm that scales well.

Example

Consider an unsorted array of integers: [38, 27, 43, 3, 9, 82, 10]. After applying a sorting algorithm, the array should be ordered as: [3, 9, 10, 27, 38, 43, 82].

Background & Knowledge Prerequisites

To effectively understand and implement Merge Sort in C, readers should be familiar with the following concepts:

• C Programming Basics: Understanding of variables, data types, loops (for, while), and conditional statements (if-else).
• Arrays: How to declare, initialize, and access elements in C arrays.
• Functions: Creating and calling functions, passing arguments, and understanding function scope.
• Recursion: The concept of a function calling itself, including defining base cases and recursive steps.
• Pointers and Dynamic Memory Allocation: Basic understanding of pointers and malloc/free for temporary array creation in the merge step.

Use Cases or Case Studies

Merge Sort's characteristics make it suitable for several practical scenarios:

• External Sorting: It is ideal for sorting massive datasets that do not fit into main memory. Data can be read in chunks, sorted, and then merged from disk.
• Sorting Linked Lists: Unlike array-based sorting algorithms that require random access (e.g., Quick Sort), Merge Sort only needs sequential access, making it highly efficient for linked lists.
• Parallel Computing: Its divide-and-conquer nature allows different sub-arrays to be sorted concurrently, making it a good candidate for parallel processing architectures.
• Inversion Count Problem: A modified version of Merge Sort can efficiently count the number of inversions in an array, which is a measure of how "unsorted" an array is.
• Data Validation and Reconciliation: When comparing two large, unsorted datasets for common elements or differences, sorting both first using Merge Sort can make the comparison process much faster.

Solution Approaches

Merge Sort operates on the "divide and conquer" paradigm, which involves three steps:

1. Divide: Split the unsorted list into n sub-lists, each containing one element (a list of one element is considered sorted).
2. Conquer: Recursively sort each sub-list.
3. Combine (Merge): Repeatedly merge sub-lists to produce new sorted sub-lists until there is only one sorted list remaining.

Approach 1: The mergeSort Function (Divide)

The mergeSort function is responsible for recursively dividing the array into two halves until individual elements are reached.

• One-line summary: Recursively divides the array into two halves until the base case of single-element arrays is met.

// Merge Sort Recursive Division
#include <stdio.h>

void mergeSort(int arr[], int left, int right) {
    // Base case: if the sub-array has one or zero elements, it's already sorted
    if (left < right) {
        // Find the middle point of the current sub-array
        int mid = left + (right - left) / 2;

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

        // After the halves are sorted, merge them (merge function would be called here)
        // merge(arr, left, mid, right);
    }
}

Run

• Stepwise explanation for clarity:

1. The mergeSort function takes the array arr and two indices, left and right, defining the boundaries of the current sub-array to be sorted.
2. The primary condition if (left < right) serves as the base case for the recursion. If left is greater than or equal to right, it means the sub-array contains one element or is empty, which is by definition sorted, so the function returns.
3. The mid index is calculated to split the current sub-array into two halves. The formula left + (right - left) / 2 is used to prevent potential integer overflow that could occur with (left + right) / 2 when left and right are very large.
4. The mergeSort function then calls itself recursively for the left half (arr, left, mid) and the right half (arr, mid + 1, right). This process continues until each sub-array consists of a single element.
5. Conceptually, after the recursive calls return (meaning the sub-arrays are sorted), a merge function (implemented in the next approach) would be called to combine these sorted halves back into a larger sorted array.

Approach 2: The merge Function (Conquer)

The merge function is the core of Merge Sort, responsible for combining two already sorted sub-arrays into a single sorted array.

• One-line summary: Merges two sorted sub-arrays back into a single sorted array.

// Merge Sorted Sub-arrays
#include <stdio.h>
#include <stdlib.h> // Required for malloc and free

void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    // Calculate sizes of the two sub-arrays
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Create temporary arrays to hold the elements of the two halves
    int* L = (int*)malloc(n1 * sizeof(int));
    int* R = (int*)malloc(n2 * sizeof(int));

    // Copy data from the original array into the 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 the original array 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 in the original array

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) { // Compare elements from both halves
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy any remaining elements of L[]
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy any remaining elements of R[]
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }

    // Free the dynamically allocated memory to prevent memory leaks
    free(L);
    free(R);
}

Run

• Stepwise explanation for clarity:

1. The merge function receives the array arr and indices left, mid, and right. mid demarcates the end of the first sorted sub-array, and mid + 1 is the start of the second.
2. It calculates n1 and n2, the sizes of the left and right sub-arrays, respectively.
3. Two temporary arrays, L and R, are dynamically allocated using malloc to store the elements of the two sub-arrays. This auxiliary space is a characteristic of Merge Sort.
4. Elements from arr (from left to mid and mid + 1 to right) are copied into L and R.
5. Three pointers (i for L, j for R, k for arr) are initialized. i and j start at the beginning of their respective temporary arrays, and k starts at the left boundary of the segment being merged in the original array.
6. In a while loop, elements from L and R are compared. The smaller element is placed into arr[k], and its corresponding pointer (i or j) is incremented, along with k.
7. After one of the temporary arrays is exhausted, any remaining elements from the other temporary array are copied directly into arr. This handles cases where one sub-array might have more elements than the other (e.g., if the original array had an odd number of elements).
8. Finally, free(L) and free(R) are called to release the memory allocated for the temporary arrays, preventing memory leaks.

Approach 3: Complete C Program for Merge Sort

This approach combines the mergeSort and merge functions into a complete, runnable C program, along with a utility function to print arrays.

• One-line summary: Full implementation of Merge Sort in C, demonstrating sorting an array from start to finish.

// Merge Sort Algorithm in C
#include <stdio.h>
#include <stdlib.h> // For malloc and free

// Function to merge two halves of an array
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 = (int*)malloc(n1 * sizeof(int));
    int* R = (int*)malloc(n2 * sizeof(int));

    // Copy data to temp arrays L[] and R[]
    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 temp 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++;
    }

    // Free the dynamically allocated memory
    free(L);
    free(R);
}

// 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 an array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\\n");
}

int main() {
    // Step 1: Define an unsorted array
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    // Step 2: Print the original array
    printf("Original array: \\n");
    printArray(arr, arr_size);

    // Step 3: Apply Merge Sort
    // Call mergeSort with the array, starting index (0), and ending index (size - 1)
    mergeSort(arr, 0, arr_size - 1);

    // Step 4: Print the sorted array
    printf("Sorted array: \\n");
    printArray(arr, arr_size);

    return 0;
}

Run

• Sample Output:

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

• Stepwise explanation for clarity:

1. The main function initiates the program by declaring an unsorted integer array arr.
2. It calculates arr_size to determine the total number of elements in the array.
3. The printArray utility function is called to display the contents of the arr before sorting.
4. The mergeSort function is invoked with arr, the starting index 0, and the ending index arr_size - 1. This call kicks off the recursive divide-and-conquer process.
5. mergeSort will recursively divide the array into smaller sub-arrays until they are single elements, then merge will be called to combine these sorted sub-arrays progressively.
6. After mergeSort completes, the printArray function is called again to display the now-sorted array.
7. return 0; indicates successful program execution.

Conclusion

Merge Sort is a powerful and reliable sorting algorithm, characterized by its consistent O(n log n) time complexity in all cases (best, average, and worst). This makes it a preferred choice for large datasets where predictable performance is critical. While it has a higher space complexity due to the temporary arrays used in the merge step, its stability and efficiency in diverse scenarios make it invaluable in computer science.

Summary

• Divide and Conquer Principle: Merge Sort operates by recursively dividing an unsorted list into n sub-lists (each with one element) and then repeatedly merging sub-lists to produce new sorted sub-lists until only one sorted list remains.
• Consistent Time Complexity: It guarantees an O(n log n) time complexity for best, average, and worst-case scenarios, making its performance highly predictable.
• Space Complexity: Requires O(n) auxiliary space due to the temporary arrays used during the merging process.
• Stability: Merge Sort is a stable sorting algorithm, preserving the relative order of equal elements in the sorted output.
• Recursive Nature: The algorithm is inherently recursive, breaking down problems into smaller, identical sub-problems.
• Key Applications: Particularly useful for external sorting, linked list sorting, and situations benefiting from parallel processing due to its independent sub-problem solving.