I really need help on this.. this is my fourth time uploading this, so please help me out.. Data Structure in C++ Using namespace std; In this assignment you will implement a variation of Mergesort known as a bitonic mergesort, recursively In a bitonic mergesort, we use the same arrangement, except that the second sequence is sorted in descending order: the first half goes up, and then the second half goes down. This means that when we are doing a merge, sometimes we want to merge the results into ascending order, while other times we want to merge into descending order (depending on which half of the final array the result will end up in). So we add another parameter, to describe the direction the output should be sorted into: 

void merge(int* input, int size, int* output, bool output_asc); 

If output_asc == true then after the merge output should contain size elements, sorted in ascending order.

If output_asc == false, output should contain the elements sorted in descending order

The other thing we glossed over in class was the allocation of the temporary space needed by the algorithm. Its quite wasteful to allocate it in each recursive call: it would be better to allocate all the necessary space up front, and then just pass a pointer to it. In order to do this, well write the recursive mergesort function in a helper function which will preallocate the space needed for the results:

int* mergesort(int* input, int size) { int* output = new int[size]; mergesort(input, size, output, true); return output; } void mergesort(int *input, int size, int* output, bool output_asc) { // Your implementation here } 

The parameter output_asc serves the same purpose here as for merge: it tells the function that we want the output to be sorted ascending.

Implement these functions: void merge(int* input, int size, int* output, bool output_asc); int* mergesort(int* input, int size); void mergesort(int *input, int size, int* output, bool output_asc); /* * mergesort.cpp * Implementation of a bitonic mergesort */ /* merge(input, size, output, asc) Merge the two halves of the array input (which has size elements) into output. If asc is true, then the output array should be in ascending order; otherwise it should be descending. */ void merge(int* input, int size, int* output, bool output_asc) { // Your merge implementation goes here } /* mergesort(input, size, output, asc) Mergesort the input array (with size elements) into the output array. If asc is true, the output array should be sorted ascending, otherwise it should be descending. */ void mergesort(int *input, int size, int* output, bool output_asc) { // Your mergesort implementation goes here } /* mergesort(input, size) Sorts size elements in the array pointed to by input, using the MergeSort algorithm. Output is returned as a newly allocated array, which the caller is responsible for freeing. */ int* mergesort(int* input, int size) { int* output = new int[size]; mergesort(input, size, output, true); return output; } 

merge must run in O(n) time with n= size. mergesort (both versions) must run in O(nlogn) time, and must use O(n) space. If you allocate any space other than the output array, you should free it before your function returns