C Program For Merge Sort Without Using Function

Merge Sort is an efficient, comparison-based sorting algorithm that divides an input array into two halves, calls itself for the two halves, and then merges the two sorted halves. In this article, you will learn how to implement an iterative (bottom-up) version of Merge Sort directly within the main function in C, adhering to the constraint of not using additional user-defined functions.

Problem Statement

Sorting an array of elements is a fundamental task in computer science, crucial for optimizing data retrieval and processing. While recursive implementations of Merge Sort are common, the challenge often arises to achieve the same efficient sorting logic without relying on user-defined functions. This requires an iterative approach, meticulously managed within a single scope, specifically the main function, which can be critical in environments with strict function call limitations or for understanding the algorithm's mechanics at a deeper level.

Example

Consider an unsorted array: [12, 11, 13, 5, 6, 7]

The expected sorted output after applying Merge Sort logic would be: [5, 6, 7, 11, 12, 13]

Background & Knowledge Prerequisites

To understand the iterative Merge Sort implementation, readers should be familiar with:

• C Array Basics: Declaring, initializing, and accessing elements in one-dimensional arrays.
• Loops: for loops for iteration and controlling program flow.
• Conditional Statements: if-else structures for decision-making.
• Pointers (optional but helpful): Understanding how pointers can be used to manipulate array elements, though direct indexing will be primarily used here.

Use Cases or Case Studies

Sorting algorithms like Merge Sort are widely used in various applications:

• External Sorting: When data to be sorted is too large to fit into memory, Merge Sort's divide-and-conquer strategy is highly effective for sorting data stored on disk.
• Data Processing: In databases and data analysis, efficient sorting is vital for indexing, querying, and preparing data for further computations.
• Custom Data Structures: Implementing custom sorted lists, priority queues, or other ordered data collections often relies on underlying sorting logic.
• Parallel Computing: Merge Sort is well-suited for parallelization because its divide-and-conquer nature allows sub-problems to be solved independently.
• Algorithm Foundations: It serves as a basis for understanding more complex algorithms and data structures, and its stable sorting property is valuable in specific scenarios.

Solution Approaches

Implementing Merge Sort without user-defined functions necessitates an iterative (bottom-up) approach. Instead of recursively breaking down the array, we start by merging small, already "sorted" sub-arrays (initially single elements) and progressively merge larger sub-arrays until the entire array is sorted. All this logic must reside within the main function.

Iterative (Bottom-Up) Merge Sort within main

This approach sorts the array by starting with merging adjacent elements, then merging pairs of sorted sub-arrays of increasing sizes directly within the main function's scope.

// Merge Sort without user-defined functions in C
#include <stdio.h>
#include <stdlib.h> // For malloc (though we'll use a fixed-size array for simplicity here)

int main() {
    // Step 1: Define the array to be sorted and its size
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    // Step 2: Declare a temporary array for merging
    // In a real-world scenario, dynamic allocation (malloc) is preferred for temp_arr
    // For simplicity and to avoid malloc/free complexity within this specific constraint,
    // we use a fixed-size array. Make sure it's large enough.
    int temp_arr[n]; // C99 VLA feature, or declare a large enough fixed size like temp_arr[100]

    // Step 3: Implement the iterative merge sort logic
    // current_size goes from 1 to n/2, doubling in each iteration
    int current_size; 
    // left_start is the starting index of the left sub-array
    int left_start;    

    // Iterate over sub-array sizes (1, 2, 4, ...)
    for (current_size = 1; current_size <= n - 1; current_size = 2 * current_size) {
        // Pick starting point of different sub-arrays of current_size
        for (left_start = 0; left_start < n - 1; left_start += 2 * current_size) {
            // Find ending point of left sub-array. mid is (left_start + current_size - 1)
            int mid = left_start + current_size - 1;

            // Find ending point of right sub-array.
            // right_end is (left_start + 2*current_size - 1)
            int right_end = left_start + 2 * current_size - 1;

            // Adjust mid and right_end to be within array bounds
            if (mid >= n) { // If left sub-array extends beyond array, adjust mid
                mid = n - 1;
            }
            if (right_end >= n) { // If right sub-array extends beyond array, adjust right_end
                right_end = n - 1;
            }

            // Perform the merge operation
            // left_start to mid is left sub-array
            // mid+1 to right_end is right sub-array
            int i, j, k;
            i = left_start;      // Index for the left sub-array
            j = mid + 1;         // Index for the right sub-array
            k = left_start;      // Index for the temporary array

            // Merge the two sub-arrays into temp_arr
            while (i <= mid && j <= right_end) {
                if (arr[i] <= arr[j]) {
                    temp_arr[k++] = arr[i++];
                } else {
                    temp_arr[k++] = arr[j++];
                }
            }

            // Copy the remaining elements of left sub-array, if any
            while (i <= mid) {
                temp_arr[k++] = arr[i++];
            }

            // Copy the remaining elements of right sub-array, if any
            while (j <= right_end) {
                temp_arr[k++] = arr[j++];
            }

            // Copy the merged elements back to the original array
            for (i = left_start; i <= right_end; i++) {
                arr[i] = temp_arr[i];
            }
        }
    }

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

    return 0;
}

Run

Sample Output

Original array: 12 11 13 5 6 7 
Sorted array: 5 6 7 11 12 13

Stepwise Explanation

1. Initialization: An integer array arr and its size n are defined. A temporary array temp_arr of the same size is declared to assist in the merging process.
2. Outer Loop (current_size): This loop controls the size of the sub-arrays being merged. It starts with 1 (merging individual elements) and doubles in each iteration (1, 2, 4, 8, etc.) until it covers the entire array.
3. Inner Loop (left_start): This loop iterates through the array, picking the starting index (left_start) of the left sub-array for each merge operation. It increments by 2 * current_size to move to the next pair of sub-arrays.
4. Define Sub-array Boundaries:

• mid: Calculates the end index of the left sub-array.
• right_end: Calculates the end index of the right sub-array.
• These indices are carefully checked and adjusted to ensure they do not exceed the actual array bounds, especially for the last sub-arrays.

1. Merge Operation:

• Three pointers (i, j, k) are used: i for the left sub-array, j for the right sub-array, and k for temp_arr.
• Elements from arr[i] and arr[j] are compared. The smaller element is copied to temp_arr[k], and its respective pointer (i or j) and k are incremented.
• After one sub-array is exhausted, the remaining elements from the other sub-array are copied directly to temp_arr.

1. Copy Back: Finally, the merged and sorted elements from temp_arr are copied back into the original arr for the current segment, completing one merge step before the next pair of sub-arrays is processed.

Conclusion

Implementing Merge Sort without user-defined functions requires a shift from the typical recursive paradigm to an iterative, bottom-up approach. This method, while more complex to manage within a single function scope, effectively demonstrates the sorting logic by incrementally merging sorted sub-arrays. It highlights a robust way to achieve efficient sorting under strict functional constraints, proving that the core principles of Merge Sort can be applied in various architectural patterns.

Summary

• Merge Sort is an efficient, comparison-based sorting algorithm.
• Implementing it without user-defined functions necessitates an iterative (bottom-up) approach.
• The solution involves two nested loops: one for current_size (size of sub-arrays) and one for left_start (start index of sub-arrays).
• A temporary array is crucial for merging sorted sub-arrays.
• The merge logic compares elements from two adjacent sub-arrays and places them in sorted order into the temporary array, then copies them back to the original array.