Lecture 350:- Let's Code Iterative Merge Sort

Here's the C++ implementation of Iterative Merge Sort:

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();    // Start with sub-arrays of size 1 and double the size in each iteration    for (int currSize = 1; currSize < n; currSize *= 2) {        // Merge adjacent pairs of sorted sub-arrays        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.