Lecture 349:- Iterative Merge Sort

Iterative Merge Sort is a variation of the Merge Sort algorithm that avoids recursion and uses an iterative approach to sort an array. Instead of dividing the array into smaller sub-arrays recursively, the iterative version directly performs merging operations in a bottom-up manner.

The basic idea of Iterative Merge Sort is to start with merging individual elements as sorted arrays of size 1, then merge adjacent pairs of sorted arrays, then merge pairs of merged arrays, and so on until the entire array is sorted.

Here's the step-by-step process for Iterative Merge Sort:

1. Start by considering each element as a sorted array of size 1.
2. Repeat the following steps until there is only one sorted array remaining: a. Traverse the array and merge adjacent pairs of sorted arrays into larger sorted arrays. b. Double the size of the sorted arrays in each iteration (i.e., merge pairs of size 1, then pairs of size 2, then pairs of size 4, and so on). c. Continue merging until only one sorted array is left.

Let's see an example of Iterative Merge Sort in C++:

cppCopy code

#include <iostream> #include <vector> using namespace std; // Function to merge two sorted arrays into a single sorted array void merge(vector<int>& arr, int left, int mid, int right) {    vector<int> temp(right - left + 1);    int i = left, j = mid + 1, k = 0;    while (i <= mid && j <= right) {        if (arr[i] <= arr[j])            temp[k++] = arr[i++];        else            temp[k++] = arr[j++];    }    while (i <= mid)        temp[k++] = arr[i++];    while (j <= right)        temp[k++] = arr[j++];    for (int p = 0; p < k; p++)        arr[left + p] = temp[p]; } // Iterative Merge Sort function void iterativeMergeSort(vector<int>& arr) {    int n = arr.size();    for (int currSize = 1; currSize < n; currSize *= 2) {        for (int left = 0; left < n - 1; left += 2 * currSize) {            int mid = min(left + currSize - 1, n - 1);            int right = min(left + 2 * currSize - 1, n - 1);            merge(arr, left, mid, right);        }    } } // Function to display the elements of the array void display(const vector<int>& arr) {    for (int val : arr)        cout << val << " ";    cout << endl; } int main() {    vector<int> arr = {38, 27, 43, 3, 9, 82, 10};    cout << "Original Array: ";    display(arr);    iterativeMergeSort(arr);    cout << "Sorted Array: ";    display(arr);    return 0; }

In this implementation, the merge function is used to merge two sorted sub-arrays. The iterativeMergeSort function performs the Iterative Merge Sort by iteratively merging adjacent pairs of sorted arrays until the entire array is sorted.

When you run this code, it will display the original array and then the sorted array after applying the Iterative Merge Sort algorithm.