Using C++, I've been trying to create this code to perform a mergesort. I have created an array of 10,000 elements and filled it with random numbers. I then implemented a mergesort function and merge function. I know there are mistakes in this section but I don't know what exactly. I then implemented a timesort function to try and determine the time it takes to perform the mergesort function. Again, in know there is a mistake when calling the mergesort function in this section and I don't know how to fix it. Lastly, in my main function, I want to display the unsorted array, the sorted array after the mergesort, and the time it took to perform the mergesort at 10,000 elements, 20,000 elements, 30,000 elements, and 40,000 elements. Please help me fix my code!

#include // Used for input and output. #include #include #include

using namespace std;

// Press any key to continue. void pressAnyKey() { cout << "Press any key to continue" << endl; _getch(); // Waits and gets next character entered. }

// Display values of array - each on their own line. void displayArray(int array[], int length) { int i = 0; while (i < length) { cout << array[i] << " "; i++; } cout << endl; }

// Give a random value to each element of the array. void randomizeArray(int array[], int length) { srand((unsigned)time(NULL)); // Seed random number generator.

int i = 0; do { array[i] = rand() % 1000000 + 1; // A random number in the range of 1 to 100,000 is assigned. i++; } while (i < length); }

// Sort array.

void merge(int*, int, int, int); void mergesort(int*, int, int); void timeSort(int array[], int length);

void mergesort(int *array, int left, int right) { int mid; if (left < right) { mid = (left + right) / 2; mergesort(array, left, mid); mergesort(array, mid + 1, right); merge(array, left, right, mid); displayArray; } }

void merge(int *array, int left, int right, int mid) { int firsthalfindex, secondhalfindex, outputindex, output[10000];

firsthalfindex = left; secondhalfindex = mid + 1; outputindex = left;

while (firsthalfindex <= mid && secondhalfindex <= right) { if (array[firsthalfindex] < array[secondhalfindex]) { output[outputindex] = array[firsthalfindex];

outputindex++; firsthalfindex++; } else { output[outputindex] = array[secondhalfindex];

outputindex++; secondhalfindex++; } } while (firsthalfindex <= mid) { output[outputindex] = array[firsthalfindex];

outputindex++; firsthalfindex++; } while (secondhalfindex <= mid) { output[outputindex] = array[secondhalfindex]; outputindex++; secondhalfindex++; } for (firsthalfindex = left; firsthalfindex < outputindex; firsthalfindex++) { array[firsthalfindex] = output[firsthalfindex]; }

}

void timeSort(int array[], int length) { clock_t startTime, endTime; // Randomize values in array. randomizeArray(array, length);

// Time array sort. startTime = clock(); // Get starting time. mergesort(array, length); // Sort array. endTime = clock(); // Get ending time.

// Display algorithm's running time as difference between starting and ending time. cout << "Mergesort time for an array of " << length << ": " << ((float)endTime - (float)startTime) / CLOCKS_PER_SEC * 1000 << " milliseconds." // On my machine, CLOCKS_PER_SEC is equal to 1000 and // thus milliseconds is the correct unit. << endl; }

int main() { const int length = 10000; // The base length of our test arrays.

int demo[length]; displayArray(demo, length);

randomizeArray(demo, length); // Randomize values in array and display. displayArray(demo, length); pressAnyKey();

mergesort(demo, length); // Test 1: Time and sort array. int test1[length]; timeSort(test1, length);

// Test 2: Time and sort array. int test2[2 * length]; timeSort(test2, 2 * length);

// Test 3: Time and sort array. int test3[3 * length]; timeSort(test3, 3 * length);

// Test 4: Time and sort array. int test4[4 * length]; timeSort(test4, 4 * length);

// End program. pressAnyKey(); return 0;

}