C++ MERGE SORT void mergeSort(int *arr, int size, int &compCount, int &moveCount);
Question:
C++ MERGE SORT
You will implement merge sort algorithm. Your function should take an array of integers and the size of that array and then sort it in increasing order. Add two counters to count the number of key comparisons and the number of data moves during sorting. Your function should have the following prototype:
void mergeSort(int *arr, int size, int &compCount, int &moveCount);
For key comparisons, you should count each comparison like k1 < k2 as one comparison, where k1 and k2 correspond to the value of an array entry (that is, they are either an array entry like arr[i] or a local variable that temporarily keeps the value of an array entry). For data moves, you should count each assignment as one move, where either the right-hand side of this assignment or its left-hand side or both of its sides correspond to the value of an array entry.
Answer:
Complete Program:
Sample Output:
CODE TO COPY:
// Header files section
#include <iostream>
#include <string>
using namespace std;
// function prototypes
void printArray(int* arr, int size);
void mergeSort(int* arr, int size, int& compCount, int& moveCount);
void mergeSortRec(int* arr, int size, int start, int end, int& compCount, int& moveCount);
void merge(int *arr, int size, int start, int middle, int end, int &compCount, int &moveCount);
// start main function
int main()
{
int size = 9;
int *arr = new int[size] {5, 9, 4, 6, 1, 8, 2, 7, 3};
int compCount = 0;
int moveCount = 0;
cout << "Array before sorting: ";
printArray(arr, size);
// call the mergeSort function
mergeSort(arr, size, compCount, moveCount);
cout << endl << "Array after sorting: ";
printArray(arr, size);
cout << "Number of key comparisons: " << compCount << endl;
cout << "Number of data moves during sorting: " << moveCount << endl;
return 0;
} // end of main function
// printArray function implementation
void printArray(int* arr, int size)
{
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl;
} // end of printArray function
// mergeSort function implementation
void mergeSort(int* arr, int size, int& compCount, int& moveCount)
{
mergeSortRec(arr, size, 0, size - 1, compCount, moveCount);
} // end of mergeSort function
// mergeSortRec function implementation
void mergeSortRec(int* arr, int size, int start, int end, int& compCount, int& moveCount)
{
if (start < end)
{
int middle = (start + end) / 2;
mergeSortRec(arr, size, start, middle, compCount, moveCount);
mergeSortRec(arr, size, middle + 1, end, compCount, moveCount);
merge(arr, size, start, middle, end, compCount, moveCount);
}
} // end of mergeSortRec function
// merge function implementation
void merge(int* arr, int size, int start, int middle, int end,
int& compCount, int& moveCount)
{
int* tempItems = new int[size]{0};
int s1 = start;
int e1 = middle;
int s2 = middle + 1;
int e2 = end;
int pos = s1;
while (s1 <= e1 && s2 <= e2)
{
compCount++;
if (arr[s1] < arr[s2])
{
tempItems[pos] = arr[s1];
moveCount++;
s1++;
}
else
{
tempItems[pos] = arr[s2];
moveCount++;
s2++;
}
pos++;
}
while (s1 <= e1)
{
tempItems[pos] = arr[s1];
moveCount++;
s1++;
pos++;
}
while (s2 <= e2)
{
tempItems[pos] = arr[s2];
moveCount++;
s2++;
pos++;
}
for (pos = start; pos <= end; pos++)
{
arr[pos] = tempItems[pos];
moveCount++;
}
} // end of merge function
