Create A Program to Implement Merge Sort Algorithm in C++ Assignment Solution.

Instructions

Objective

Write a C++ assignment program to implement merge sort algorithm.

Requirements and Specifications

You are given the C++ code for the Merge Sort algorithm. The code as such would input the array size value, then generate/print a random array of specified size with values ranging from 1 to 50 and output the sorted array.

Your task in this assignment is to modify the code for the algorithm to determine the number of inversions in an array as well as print the inverted pairs.

After the enhancement, the output of the code should be both the initial randomly generated array and the final sorted array as well as the number of inversions in the initial randomly generated array and the inverted pairs accounting for the number of inversions.

Screenshot

Source Code

#include #include //srand, rand #include //clock_t, clock, CLOCKS_PER_SEC #include #include #include using namespace std; void PrintArray(int* arrayPtr, int arraySize){ for (int i = 0; i < arraySize; i++) cout << arrayPtr[i] << " "; cout << endl; } long Merge(int* leftSubArrayPtr, int leftArraySize, int *rightSubArrayPtr, int rightArraySize, int *arrayPtr, int arraySize){ int leftIndex = 0; int rightIndex = 0; int arrayIndex = 0; long counter = 0; while (leftIndex < leftArraySize && rightIndex < rightArraySize){ if (leftSubArrayPtr[leftIndex] <= rightSubArrayPtr[rightIndex]){ arrayPtr[arrayIndex] = leftSubArrayPtr[leftIndex]; leftIndex++; } else{ arrayPtr[arrayIndex] = rightSubArrayPtr[rightIndex]; counter += leftArraySize - leftIndex; for(int i = leftIndex; i < leftArraySize; i++) { cout << leftSubArrayPtr[i] << " " << rightSubArrayPtr[rightIndex] << endl; } rightIndex++; } arrayIndex++; } if (leftIndex == leftArraySize){ for (; rightIndex < rightArraySize; rightIndex++){ arrayPtr[arrayIndex] = rightSubArrayPtr[rightIndex]; arrayIndex++; } } else{ for (; leftIndex < leftArraySize; leftIndex++){ arrayPtr[arrayIndex] = leftSubArrayPtr[leftIndex]; arrayIndex++; } } return counter; } long MergeSort(int* arrayPtr, int arraySize){ if (arraySize > 1) { int* leftSubArrayPtr = new int[arraySize/2]; int* rightSubArrayPtr = new int[arraySize - arraySize/2]; for (int i = 0; i < (arraySize/2); i++) leftSubArrayPtr[i] = arrayPtr[i]; for (int i = arraySize/2; i < arraySize; i++) rightSubArrayPtr[i-(arraySize/2)] = arrayPtr[i]; long leftInvs = MergeSort(leftSubArrayPtr, arraySize/2); long rightInvs = MergeSort(rightSubArrayPtr, arraySize - arraySize/2); long mergeInvs = Merge(leftSubArrayPtr, arraySize/2, rightSubArrayPtr, arraySize - arraySize/2, arrayPtr, arraySize); return leftInvs + rightInvs + mergeInvs; } else { return 0; } } int main(){ int arraySize; cout << "Enter array size: "; cin >> arraySize; int maxVal = 50; srand(time(NULL)); int* arrayPtr = new int[arraySize]; for (int i = 0; i < arraySize; i++) arrayPtr[i] = 1 + rand() % maxVal; cout << "Before sorting..." << endl; PrintArray(arrayPtr, arraySize); cout << "Inversions: " << endl; long invs = MergeSort(arrayPtr, arraySize); cout << "Number of Inversions: " << invs << endl; cout << "After sorting..." << endl; PrintArray(arrayPtr, arraySize); system("pause"); return 0; }