C++ Program For Merge Sort Without Using Function

Merge Sort is an efficient, comparison-based sorting algorithm that uses a divide-and-conquer strategy. It operates by breaking down an unsorted list into several sublists until each sublist contains only one element, then repeatedly merges these sublists to produce new sorted sublists until there is only one sorted list remaining. In this article, you will learn how to implement the Merge Sort algorithm in C++ without defining or using any custom functions, performing all operations within the main function.

Problem Statement

The goal is to sort an array of integers using the Merge Sort algorithm. The specific constraint is to achieve this *without* using any user-defined functions, meaning all the logic, including the splitting and merging steps, must reside directly within the main function. This presents a unique challenge as Merge Sort is typically implemented recursively or with helper functions for clarity and modularity. This exercise demonstrates a deeper understanding of array manipulation and iterative control flow required when bypassing standard functional decomposition.

Example

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

After applying the iterative merge sort logic entirely within the main function, the array will be sorted as:

[5, 6, 7, 11, 12, 13]

Background & Knowledge Prerequisites

To understand the implementation of Merge Sort without functions, readers should be familiar with:

• C++ Basics: Fundamental syntax, variable declarations, loops (for, while).
• Arrays: Declaring, initializing, and accessing elements of one-dimensional arrays.
• Pointers (Optional but helpful for understanding memory): Though not explicitly used in the simplest array index-based solution, understanding how arrays relate to contiguous memory helps.
• Basic Sorting Concepts: An awareness of what sorting entails and simple algorithms like bubble sort or insertion sort can provide context.
• Iterative Control Flow: How to manage iterations and nested loops to process sub-problems sequentially.

Relevant setup: No special libraries are needed beyond the standard input/output stream for C++.

#include <iostream>
// Using namespace std; will be included in the full program for brevity.

Use Cases or Case Studies

Merge Sort is valued for its stability and guaranteed O(N log N) time complexity, making it suitable for various scenarios:

• Large Datasets: Efficiently sorts large arrays or lists of data where performance is critical.
• External Sorting: Ideal for sorting data that does not fit into RAM, as it can efficiently merge sorted chunks from disk.
• Linked Lists: Particularly well-suited for sorting linked lists because it requires O(1) extra space complexity (ignoring recursion stack space) for linked lists, unlike arrays where an auxiliary array is often needed for merging.
• Inversion Counting: A common application in competitive programming where the number of inversions (pairs of elements that are out of order) in an array needs to be counted.
• Parallel Computing: Its divide-and-conquer nature makes it amenable to parallelization.

Solution Approaches

Implementing Merge Sort without functions necessitates an *iterative* (bottom-up) approach, as recursion inherently involves function calls. The core idea is to start by merging sub-arrays of size 1, then size 2, then size 4, and so on, until the entire array is sorted.

Approach 1: Iterative Bottom-Up Merge Sort in main

This approach implements the entire Merge Sort logic—the loop for current_size and the inner loop for left_start, along with the merging process—directly within the main function.

One-line summary: An iterative, bottom-up Merge Sort performed entirely within the main function using nested loops and a temporary array for merging.

Code example:

// Iterative Merge Sort Without Functions
#include <iostream>
#include <vector> // Using vector for dynamic array behavior, though raw arrays could also be used.
#include <algorithm> // For std::min, which is helpful.

int main() {
    std::cout << "Iterative Merge Sort without using functions." << std::endl;

    // Step 1: Initialize the unsorted array
    int arr[] = {12, 11, 13, 5, 6, 7, 2, 9, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Original array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    // Step 2: Create a temporary array for merging
    // A C-style array can also be used: int temp_arr[n];
    std::vector<int> temp_arr(n);

    // Step 3: Implement the iterative merge sort logic
    // current_size is the size of sub-arrays to be merged
    for (int current_size = 1; current_size < n; current_size = 2 * current_size) {
        // Pick starting point of different sub-arrays of current_size
        for (int left_start = 0; left_start < n - 1; left_start += 2 * current_size) {
            // Find ending point of left sub-array (mid)
            // mid is ((left_start + current_size) - 1)
            int mid = std::min(left_start + current_size - 1, n - 1);

            // Find ending point of right sub-array
            int right_end = std::min(left_start + 2 * current_size - 1, n - 1);

            // Merge sub-arrays arr[left_start...mid] and arr[mid+1...right_end]

            int i = left_start;        // Initial index for left sub-array
            int j = mid + 1;           // Initial index for right sub-array
            int k = left_start;        // Initial index for merged sub-array in temp_arr

            while (i <= mid && j <= right_end) {
                if (arr[i] <= arr[j]) {
                    temp_arr[k] = arr[i];
                    i++;
                } else {
                    temp_arr[k] = arr[j];
                    j++;
                }
                k++;
            }

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

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

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

    // Step 4: Print the sorted array
    std::cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

Run

Sample output:

Iterative Merge Sort without using functions.
Original array: 12 11 13 5 6 7 2 9 1 
Sorted array: 1 2 5 6 7 9 11 12 13

Stepwise explanation for clarity:

1. Initialization: An integer array arr is declared and initialized with unsorted values. Its size n is calculated. A temporary std::vector temp_arr of the same size is created to assist in merging.
2. Outer Loop (current_size): This loop controls the size of the sub-arrays being merged. It starts with current_size = 1 (merging single elements into sorted pairs) and doubles in each iteration (current_size = 2 * current_size) until current_size is greater than or equal to n.
3. Inner Loop (left_start): This loop iterates through the array, picking the starting index (left_start) of consecutive sub-arrays to be merged for the current current_size. It increments by 2 * current_size in each step to move to the next pair of sub-arrays.
4. Define Sub-array Boundaries:

• mid: Calculates the end index of the left sub-array. It's left_start + current_size - 1, capped at n - 1 to prevent exceeding array bounds.
• right_end: Calculates the end index of the right sub-array. It's left_start + 2 * current_size - 1, also capped at n - 1.

1. Merging Process:

• Three pointers i, j, and k are used: i for the left sub-array (arr[left_start...mid]), j for the right sub-array (arr[mid+1...right_end]), and k for the temp_arr where merged elements are stored.
• The while (i <= mid && j <= right_end) loop compares elements from both sub-arrays and copies the smaller one to temp_arr[k], incrementing the respective pointer (i or j) and k.
• After one of the sub-arrays is exhausted, the remaining elements of the other sub-array (if any) are copied directly to temp_arr.

1. Copy Back: Finally, the sorted elements from temp_arr within the range [left_start...right_end] are copied back to the original arr. This completes one merge operation.
2. Repeat: The loops continue until all sub-arrays are merged, and the arr becomes fully sorted.
3. Output: The sorted array is printed to the console.

Conclusion

Implementing Merge Sort without using functions, especially entirely within main, demonstrates a deep understanding of iterative algorithm design and explicit array boundary management. While typically, Merge Sort benefits significantly from functions for modularity and readability (e.g., a dedicated merge function), this exercise highlights the core mechanics of the algorithm: the systematic merging of increasingly larger sorted sub-arrays until the whole data set is ordered. It underscores the challenges of managing code complexity when standard functional abstraction is foregone.

Summary

• Merge Sort is a stable, comparison-based sorting algorithm with O(N log N) time complexity.
• Problem: Implement Merge Sort in C++ *without* defining or using custom functions, confining all logic to main.
• Approach: An iterative (bottom-up) Merge Sort is necessary to avoid recursion.
• Mechanism: It involves an outer loop for current_size (1, 2, 4, ...), an inner loop for left_start to define sub-array boundaries, and a merging phase using a temporary array.
• Benefits (of Merge Sort in general): Efficient for large datasets, stable sort, suitable for external sorting and linked lists.
• Key Takeaway (from constraint): Implementing complex algorithms without functional abstraction makes code verbose and difficult to maintain, but it provides valuable insight into the low-level execution flow and array manipulation.