You will implement merge sort algorithm. Your function should take an array of i

Question

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

void merge(int *arr, int l, int m, int r, int &compCount, int &moveCount)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

int L[n1], R[n2];

for (i = 0; i < n1; i++) {
moveCount = moveCount += 1;
L[i] = arr[l + i];
}
for (j = 0; j < n2; j++) {
moveCount = moveCount += 1;
R[j] = arr[m + 1+ j];
}
  
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
compCount += 1;
moveCount += 1;
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}

while (i < n1)
{
moveCount += 1;
arr[k] = L[i];
i++;
k++;
}

while (j < n2)
{
moveCount += 1;
arr[k] = R[j];
j++;
k++;
}
}

void mergeSort(int arr[], int l, int r, int &compCount, int &moveCount)
{
if (l < r)
{
int m = l+(r-l)/2;
mergeSort(arr, l, m, compCount, moveCount);
mergeSort(arr, m+1, r, compCount, moveCount);

merge(arr, l, m, r, compCount, moveCount);
}
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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