In this assignment you will implement a variation of Mergesort known as a bitonic mergesort, recursively.
In a normal mergesort, the input to the merge
step is a single array,
which is divided into two sections, both sorted ascending. We assume that the
first half (0 up to but not including size/2
) is the first section and the
second half (size/2
up to but not including size
) is the second section.
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. It’s 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, we’ll write
the recursive mergesort
function in a helper function which will preallocate
the space needed for the results:
// You can just copy this function into your code as-is.
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.
Interface
You must implement the 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);
Download a template .cpp file containing these definitions.
This file is also available on the server in /usr/local/class/src
.
merge
must run in \(O(n)\) time with \(n = \)size
. mergesort
(both
versions) must run in \(O(n \log n)\) 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.
The test runner will test each function separately, and then in combination. It checks the result of sorting to make sure that it’s actually sorted, and then nothing is missing or added from the original (unsorted) sequence.
Testing
You can download assign3_test.cpp
or copy it
from /usr/local/class/src
on the server. The test runner will test your
code with arrays of various sizes, making sure that the results contain everything
that the input did.
Submission
Save your work in a directory on the server named cs133/assign3/
.