C Program Of Simple Merge Sort Implementation Using Array In Ascending Order

Sorting data efficiently is a fundamental task in computer science, crucial for optimizing search operations, database management, and various algorithmic processes. In this article, you will learn how to implement the Merge Sort algorithm in C to sort an array of integers in ascending order.

Problem Statement

The challenge lies in organizing a disordered collection of elements into a specific sequence, typically ascending or descending. While simpler sorting algorithms like Bubble Sort exist, they become inefficient for large datasets. We need a robust algorithm that performs well even with many elements, providing a consistent and predictable time complexity.

Example

Consider an unsorted array of integers. After applying Merge Sort, the elements will be arranged in ascending order.

Input Array: [38, 27, 43, 3, 9, 82, 10] Sorted Output: [3, 9, 10, 27, 38, 43, 82]

Background & Knowledge Prerequisites

To understand and implement Merge Sort, readers should be familiar with:

• C Programming Basics: Variables, data types, loops (for, while), conditional statements (if-else).
• Arrays: Declaring, initializing, and accessing elements.
• Functions: Defining and calling functions, passing arguments by value and reference.
• Recursion: Understanding how functions call themselves and the concept of a base case.
• Pointers: Basic understanding for array manipulation.

Use Cases or Case Studies

Merge Sort is a powerful algorithm applied in various scenarios due to its stability and efficiency:

• External Sorting: When data is too large to fit into memory, Merge Sort can efficiently sort chunks of data on disk and then merge them.
• Parallel Sorting: Its divide-and-conquer nature makes it suitable for parallel implementations, where different parts of the array can be sorted concurrently.
• Linked Lists Sorting: Merge Sort is particularly efficient for sorting linked lists because it doesn't require random access to elements, only sequential access.
• Inversion Count Problem: It can be modified to count inversions in an array, a common problem in competitive programming and data analysis.
• Data Validation and Uniqueness Checks: Sorting data first makes it easier to identify duplicates or validate data integrity.

Solution Approaches

Merge Sort is a classic example of a divide-and-conquer algorithm. It works by recursively dividing the array into halves until each sub-array contains only one element (which is inherently sorted). Then, it repeatedly merges these sub-arrays to produce new sorted sub-arrays until there is only one sorted array remaining.

Approach 1: Recursive Merge Sort Implementation

This approach involves two main functions: mergeSort for dividing the array and merge for combining sorted sub-arrays.

One-line summary

Recursively divides the array into two halves, sorts them, and then merges the sorted halves back together.

Code example

// Merge Sort Implementation
#include <stdio.h>
#include <stdlib.h> // For malloc and free

// Merges two sorted sub-arrays into a single sorted 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 temporary 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 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 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++;
    }

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

// Main function that implements Merge Sort
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        // Find the middle point
        int mid = left + (right - left) / 2;

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

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

// Utility 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: Initialize an unsorted array
    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);

    // Step 2: Call mergeSort to sort the array
    mergeSort(arr, 0, arr_size - 1);

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

    return 0;
}

Run

Sample output

Given array is 
38 27 43 3 9 82 10 
Sorted array is 
3 9 10 27 38 43 82

Stepwise explanation

1. mergeSort(arr, left, right) Function:

• Base Case: If left is greater than or equal to right, it means the sub-array has 0 or 1 element, which is already sorted. The recursion stops.
• Divide: Calculate mid, the middle index of the current sub-array arr[left...right].
• Conquer (Recursively Sort):
• Call mergeSort(arr, left, mid) to sort the first half.
• Call mergeSort(arr, mid + 1, right) to sort the second half.
• Combine (Merge): Once both halves are sorted, call merge(arr, left, mid, right) to merge them into a single sorted sub-array.

1. merge(arr, left, mid, right) Function:

• Sub-array Sizes: Calculate n1 (size of the left sub-array arr[left...mid]) and n2 (size of the right sub-array arr[mid+1...right]).
• Temporary Arrays: Create two temporary arrays, L and R, of sizes n1 and n2 respectively. These will hold the elements of the two halves.
• Copy Data: Copy elements from arr[left...mid] into L and arr[mid+1...right] into R.
• Merge:
• Use three pointers: i for L, j for R, and k for the original arr (starting at left).
• Compare L[i] and R[j]. The smaller element is placed into arr[k], and its respective pointer (i or j) and k are incremented.
• This process continues until one of the temporary arrays is exhausted.
• Copy Remaining: Any remaining elements in L or R (if one sub-array was longer than the other) are copied directly into arr.
• Free Memory: Deallocate the memory used by the temporary arrays L and R to prevent memory leaks.

1. main() Function:

• Initializes an unsorted integer array.
• Prints the original array.
• Calls mergeSort with the array, starting index (0), and ending index (arr_size - 1).
• Prints the sorted array.

Conclusion

Merge Sort is an efficient, stable, and widely used sorting algorithm. Its divide-and-conquer strategy ensures a time complexity of O(n log n) in all cases (worst, average, and best), making it highly suitable for large datasets where consistent performance is critical. While it uses additional space for temporary arrays, its reliability and ability to handle various data structures make it a valuable tool in a programmer's arsenal.

Summary

• Merge Sort is a divide-and-conquer sorting algorithm.
• It operates by recursively splitting an array into halves until individual elements are reached.
• Sorted sub-arrays are then merged back together in ascending order.
• It guarantees O(n log n) time complexity for all cases.
• Requires O(n) auxiliary space for temporary arrays during the merge operation.
• It is a stable sorting algorithm, preserving the relative order of equal elements.