Question

In C++

Write an IterativeMergeSort function given these parameters and following the prompt

IterativeMergeSort(vector<int> v, int low, int high)

IterativeMergeSort

In-place sorting refers to sorting that does not require extra memory arrays. For

example, QuickSort performs partitioning operations by repeating a swapping operation on two

data items in a given array. This does not require an extra array.

We can improve the performance of MergeSort by utilizing a non-recursive method and

using only one additional array (instead of one array on each recursive call). In this improved

version of MergeSort,

IterativeMergeSort

, one would merge data from the original array into

the additional array and

alternatively

copy back and forth between the original and the

additional temporary array.

Please re-read the last sentence as it is critical to the grading of

the lab.

For the IterativeMergeSort we still need to allow data items to be copied between the

original and this additional array as many times as O(

log

n). However, given the iterative nature

we are not building up state on the stack.

Answer 1

Hello,

Please find below logic code for iterative merge sort in C/C++,

Note: here I have used Array instead vector for better get/put. if you want, you can modify your function's input to array or modify below code from array to vector.

This code was written for lector's note 3 years back. Hope this will help you.

CODE:

/* Recursive program for merge sort */

#include<stdlib.h>

#include<stdio.h>

  

/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */

void merge(int arr[], int l, int m, int r);

  

/* l is for left index and r is right index of the sub-array of arr to be sorted */

void mergeSort(int arr[], int l, int r)

{

   if (l < r)

   {

      int m = l+(r-l)/2; //Same as (l+r)/2 but avoids overflow for large l & h

      mergeSort(arr, l, m);

      mergeSort(arr, m+1, r);

      merge(arr, l, m, r);

   }

}

  

/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */

void merge(int arr[], int l, int m, int r)

{

    int i, j, k;

    int n1 = m - l + 1;

    int n2 = r - m;

  

    /* create temp arrays */

    int L[n1], R[n2];

  

    /* Copy data to temp arrays L[] and R[] */

    for (i = 0; i < n1; i++)

        L[i] = arr[l + i];

    for (j = 0; j < n2; j++)

        R[j] = arr[m + 1+ j];

  

    /* Merge the temp arrays back into arr[l..r]*/

    i = 0;

    j = 0;

    k = l;

    while (i < n1 && j < n2)

    {

        if (L[i] <= R[j])

        {

            arr[k] = L[i];

            i++;

        }

        else

        {

            arr[k] = R[j];

            j++;

        }

        k++;

    }

  

    /* Copy the remaining elements of L[], if there are any */

    while (i < n1)

    {

        arr[k] = L[i];

        i++;

        k++;

    }

  

    /* Copy the remaining elements of R[], if there are any */

    while (j < n2)

    {

        arr[k] = R[j];

        j++;

        k++;

    }

}

  

/* Function to print an array */

void printArray(int A[], int size)

{

    int i;

    for (i=0; i < size; i++)

        printf("%d ", A[i]);

    printf("\n");

}

  

/* Driver program to test above functions */

int main()

{

    int arr[] = {12, 11, 13, 5, 6, 7};

    int arr_size = sizeof(arr)/sizeof(arr[0]);

  

    printf("Given array is \n");

    printArray(arr, arr_size);

  

    mergeSort(arr, 0, arr_size - 1);

  

    printf("\nSorted array is \n");

    printArray(arr, arr_size);

    return 0;

}