In C++, do an iterative (non-recursive) merge sort using one additional array as
ID: 3831376 • Letter: I
Question
In C++, do an iterative (non-recursive) merge sort using one additional array as a semi in-place method. Merge data from the original into the additional array at the very bottom stage, and thereafter perform the next merge from the additional into the original array, in which way merge operations are applied to the original and additional array in turn as you go through each repetitive stage. Example: at the first merge, data is from original to additional array, and the next merge, data is from additional to original array.
Please provide any additional functions that are used to create this iterative merge sort.
The function at the bottom is to start out with.
Explanation / Answer
#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);
// Utility function to find minimum of two integers
int min(int x, int y) { return (x<y)? x :y; }
/* Iterative mergesort function to sort arr[0...n-1] */
void mergeSort(int arr[], int n)
{
int curr_size; // For current size of subarrays to be merged
// curr_size varies from 1 to n/2
int left_start; // For picking starting index of left subarray
// to be merged
// Merge subarrays in bottom up manner. First merge subarrays of
// size 1 to create sorted subarrays of size 2, then merge subarrays
// of size 2 to create sorted subarrays of size 4, and so on.
for (curr_size=1; curr_size<=n-1; curr_size = 2*curr_size)
{
// Pick starting point of different subarrays of current size
for (left_start=0; left_start<n-1; left_start += 2*curr_size)
{
// Find ending point of left subarray. mid+1 is starting
// point of right
int mid = left_start + curr_size - 1;
int right_end = min(left_start + 2*curr_size - 1, n-1);
// Merge Subarrays arr[left_start...mid] & arr[mid+1...right_end]
merge(arr, left_start, mid, right_end);
}
}
}
/* 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(" ");
}
/* Driver program to test above functions */
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Given array is ");
printArray(arr, n);
mergeSort(arr, n);
printf(" Sorted array is ");
printArray(arr, n);
return 0;
}
Output:
Given array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13