## Instructions

**Objective**

## Requirements and Specifications

**Source Code**

#include <iostream.h>

#include <stdlib.h> //srand, rand

#include <time.h>//clock_t, clock, CLOCKS_PER_SEC

#include <ctime.h>

#include <ratio.h>

#include <chrono.h>

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;

}

## Related Samples

Discover our curated C++ Assignments samples designed to bolster your programming skills. Explore topics including object-oriented programming, data structures, algorithms, and more. Each sample offers detailed explanations and solutions to help you excel in your coursework. Enhance your C++ proficiency with our comprehensive collection of assignments.

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++