C++ MERGE SORT You will implement merge sort algorithm. Your function should tak

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.

Explanation / Answer

#include #include // Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] 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

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.