Assignment 3: Recursion and sorting

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” is the first section and the second “half” is the second section. In a normal mergesort, the dividing line between the two sections is always at size/2, this is not necessary for merge to function correctly; merge will work just fine if the first section is everything at indexes < size/4 while the second section is everything ≥ size/4.

In a bitonic mergesort, we use the same arrangement, except that the second section 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.

Note: Although the bitonic merge function will only ever be called with the division point between the ascending and descending sequences at exactly index size/2 (input[size/2-1] is the last element of the ascending sequence while input[size/2] is the first element of the descending sequence), your code must be able to handle merging inputs where the division between the two sections occurs anywhere. It is even possible that the descending sequence is empty (meaning the entire sequence is ascending) or the ascending sequence is empty (meaning the entire sequence is descending). These are still valid bitonically-sorted sequences!

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, a helper function is provided which pre-allocates the temporary space once; your implementations should not allocate any additional dynamic memory.

int* mergesort(int* input, int size);

Hence you only have to implement the recursive mergesort function:

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);
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/mergesort.cpp.

Requirements

• merge must run in \(O(n)\) time with \(n = \)size.

• mergesort must run in \(O(n \log n)\) time, and must use \(O(n)\) space.

• Both merge and mergesort (the recursive function) should use \(O(1)\) memory (MergeSort, as an algorithm, requires \(O(n)\) memory, but the temporary space is allocated for you, so your functions should not need to allocate any additional memory.)

• After calling mergesort(input, n, output, true) the output array should contain a permutation of the values in input in ascending order. n may be any value ≥ 0.

• After calling mergesort(input, n, output, false) the output array should contain a permutation of the values in input in descending order.

• Before calling merge(input, n, output, true), input will contain a bitonically-sorted sequence (first possibly-empty section ascending, second possibly-empty section descending). After calling merge with output_asc == true, output should contain a permutation of input in ascending order.

• After calling merge(input, n, output, false), output should contain a permutation of input sorted in descending order.

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/.