C++ • SORTING ALGORITHM Iterative Merge Sort

C++ • SORTING ALGORITHM

Iterative Merge Sort

ALGORITHM

Iterative Merge Sort

TIME COMPLEXITY

O(n log n)

SPACE COMPLEXITY

O(n)

ORDER

Ascending

C++ Implementation

iterative_merge_sort.cpp

#include <iostream>
#include <algorithm>
using namespace std;

class ArraySort
{
    int n;
    int a[100];

    // Helper function to merge two sorted halves
    void merge(int low, int mid, int high)
    {
        int temp[100];
        int left = low;
        int right = mid + 1;
        int k = 0;

        while (left <= mid && right <= high)
        {
            if (a[left] <= a[right])
            {
                temp[k++] = a[left++];
            }
            else
            {
                temp[k++] = a[right++];
            }
        }

        while (left <= mid)
        {
            temp[k++] = a[left++];
        }

        while (right <= high)
        {
            temp[k++] = a[right++];
        }

        for (int i = low; i <= high; i++)
        {
            a[i] = temp[i - low];
        }
    }

public:

    // Constructor
    ArraySort()
    {
        n = 0;
    }

    // Input function
    void input()
    {
        cout << "Enter length of array: ";
        cin >> n;

        cout << "Enter array elements: ";

        for(int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
    }

    // Iterative Merge Sort function
    void mergeSort()
    {
        for (int curr_size = 1; curr_size <= n - 1; curr_size = 2 * curr_size)
        {
            for (int left_start = 0; left_start < n - 1; left_start += 2 * curr_size)
            {
                int mid = min(left_start + curr_size - 1, n - 1);
                int right_end = min(left_start + 2 * curr_size - 1, n - 1);

                merge(left_start, mid, right_end);
            }
        }
    }

    // Output function
    void output()
    {
        cout << "Sorted Array: ";

        for(int i = 0; i < n; i++)
        {
            cout << a[i] << " ";
        }
    }
};

int main()
{
    ArraySort obj;

    obj.input();
    obj.mergeSort();
    obj.output();

    return 0;
}

Sample Input

Enter length of array: 5
Enter array elements:
5 3 4 1 2

Output

Sorted Array:
1 2 3 4 5

Line-by-Line Explanation

Code

Meaning

#include <iostream>

Includes standard input/output stream functions.

#include <algorithm>

Includes std::min function used for boundary calculations.

class ArraySort

Creates a class named ArraySort containing the array and sorting methods.

int n;

Stores the total number of elements in the array.

int a[100];

Declares an integer array capable of holding up to 100 elements.

void merge(int low, int mid, int high)

Merges two sorted sub-arrays into a single sorted range using a temporary array.

ArraySort()

Class constructor that initializes object properties when instantiated.

n = 0;

Initializes the array size variable to zero.

void input()

Reads the array size and elements from the user.

for (int curr_size = 1; ...)

Iterates bottom-up, doubling the size of sub-arrays to be merged in each pass (1, 2, 4, 8, ...).

for (int left_start = 0; ...)

Iterates through the array to pick pairs of sub-arrays of size curr_size to merge.

int mid = min(...)

Calculates the ending index of the first sub-array.

int right_end = min(...)

Calculates the ending index of the second sub-array.

void output()

Displays the final sorted array to the console.

ArraySort obj;

Instantiates the ArraySort object and triggers the constructor.

return 0;

Signals successful program execution.

How iterative merge sort works: Instead of using recursion (top-down), iterative merge sort works in a bottom-up manner. It starts by merging sub-arrays of size 1 into sorted pairs of size 2, then merges pairs of size 2 into sorted blocks of size 4, and continues doubling the block size until the entire array is sorted.