So for my assignment I need to implement a recursive bitonic mergesort that takes the input array, size, output array, and output_asc where true ascends and false descends.
There is a helper function in the test runner so I don't need to allocate extra memory for the left half and right half so I'm lost in the recursion when calling mergesort for left half and right half.
Can someone check my code to see what I'm doing wrong?
Code:
#include<iostream>
void merge(int *input, int size, int *output, bool output_asc)
{
int mid = size / 2;
int i = 0;
int j = size - 1;
int k = 0;
if (output_asc) {
while (i < mid && j >= mid) {
if (input <= input[j])
output[k++] = input[i++];
else
output[k++] = input[j--];
}
} else {
while (i < mid && j >= mid) {
if (input >= input[j])
output[k++] = input[i++];
else
output[k++] = input[j--];
}
}
// Copy the remaining elements from the first section
while (i < mid) {
output[k++] = input[i++];
}
// Copy the remaining elements from the second section
while (j >= mid) {
output[k++] = input[j--];
}
}
void mergesort(int *input, int size, int *output, bool output_asc)
{
if (size == 0)
return;
else if (size == 1) {
output[0] = input[0];
} else {
int mid = size / 2;
mergesort(input, mid, output, true);
mergesort(input + mid, size - mid, output + mid, false);
for (int i = 0; i < size; ++i)
input = output;
merge(input, size, output, output_asc);
}
}
int main()
{
// Example usage
const int size = 8;
int input = { 4, 2, 7, 1, 5, 8, 3, 6 };
int output;
// Ascending order
mergesort(input, size, output, true);
std::cout << "Sorted in ascending order: ";
for (int i = 0; i < size; i++) {
std::cout << output << " ";
}
std::cout << std::endl;
// Descending order
mergesort(input, size, output, false);
std::cout << "Sorted in descending order: ";
for (int i = 0; i < size; i++) {
std::cout << output << " ";
}
std::cout << std::endl;
return 0;
}