Example: Iterative Merge Sort Without Functions in C++

// 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;
}