How do I correctly create a mergesort function?

Question

This is for my computer science c++ data structures class.

For my assignment I have to create mergesort code for ascending and descending arrays.

My professor has me compile his test code along with my file code. The terminal will print out any errors in my coding logic.

This is the error that prints out in the terminal when I run my file:

   **** Testing mergesort ****

Testing simple two-element merge:
OK

Testing 20-element merge (10 and 10): OK

Testing 21-element merge: OK

Sorting empty sequence:OK

Sorting random vector of size 2:
{48, 77}
OK

Sorting random vector of size 3:
{48, 77, 64}
OK

Sorting random vector of size 4:
{48, 77, 64, 2}
OK

Sorting random vector of size 5:
{48, 77, 64, 2, 11}

FAILED: result is not sorted:
{11, 2, 48, 64, 77}

This is my code:

void merge(int *input, int size, int *output, bool output_asc) {
    if (output_asc == true) { //sort ascending
        int i = 0;
        int j = size - 1;
        int k = 0;
        while (i <= j) {
            if (input[i] <= input[j]) {
                output[k++] = input[i++];
            } else {
                output[k++] = input[j--];
            }
        }
    } else
    if (output_asc == false) { //sort descending
        int i = 0;
        int j = size - 1;
        int k = 0;
        while (i <= j) {
            if (input[i] <= input[j]) {
                output[k++] = input[j--];
            } else {
                output[k++] = input[i++];
            }
        }
    }
}
     
void mergesort(int *input, int size, int *output, bool output_asc) {
    int begin = 0;
    int end = size - 1;
    if (begin >= end) {
        return;
    }
    int mid = (begin + end) / 2;

    mergesort(input, mid - 1, output, output_asc);
    mergesort(input, end, output, output_asc);

    merge(input, size, output, output_asc); 
}

int *mergesort(int *input, int size) {
    int *output = new int[size];
    mergesort(input, size, output, true);
    return output;
}

This is my professors test code:

/* test_mergesort()
Test mergesort on a variety of inputs.
*/
bool test_mergesort() {
    cout << "Sorting empty sequence:";
    vector<int> no_data;

    int *no_data_sorted = mergesort(no_data);
    // No data means nothing to check!
    delete[] no_data_sorted;
    cout << "OK\n";

    vector<int> sizes = { 2, 3, 4, 5, 7, 8, 15, 16, 19, 20, 50, 64, 100, 128 };

    for (int s : sizes) {

        // Test sorting a vector of random data
        vector<int> data = make_random_vector(s);

        cout << "Sorting random vector of size " << s << ":\n" << data << "\n";

        int *data_sorted = mergesort(data);
        if (!is_sorted(data_sorted, data.size())) {
            cout << "FAILED: result is not sorted:\n";

            cout << "{";
            for (int *i = data_sorted; i != data_sorted + data.size() - 1; ++i)
                cout << *i << ", ";
            cout << data_sorted[data.size() - 1] << "}\n";

            return false;
        } else
        if (!is_permutation(&data[0], data.size(), data_sorted)) {
            cout << "FAILED: result is not a permutation of the input sequence:\n";
            cout << "{";
            for (int *i = data_sorted; i != data_sorted + data.size() - 1; ++i)
                cout << *i << ", ";
            cout << data_sorted[data.size() - 1] << "}\n";

            return false;
        } else
            cout << "OK\n";
    }    
    return true;
}

Any help will be appreciated, thank you.

Answer 1

Your mergesort looks stupidly complex. Start with a simple inefficient version that is correct.

Then replace parts to make it more efficient.

std::vector<int> merge( std::vector<int> a, std::vector<int> b );

this is 20x easier to write. Write it and test it.

Then write

std::vector<int> merge_sort( std::vector<int> in );

with a simple inefficient divide, recurse, then merge.

Test and confirm it works.

Now hook it up to your professors test code. Inefficiently; copy the pointer and size to a vector, do the sort, then copy it back. Confirm your professors tests pass.

If you really want the reverse feature, add it. Add a bool to merge saying return its result backwards, and assume the right argument is backwards.

Next, write inefficient wrappers around merge that convert pointers to vectors and back. It takes two pointers and two sizes, and assumes the right one is backwards, just like the vector version.

Test it on some data. Be confident you got allocation right.

Write merge sort takes a std vector and calls those pointer-wrapped version of merge. Test it with professors code.

Now you have a reliable pointer based merge test harness.

Take the outer merge sort, and make it take pointers as input and call pointer based merge. Test with professors test harness.

Now take the inner merge function and replace it with one that uses pointers internally.

The basic idea is do it simple and correct first. Then make it possible to replace a piece with something more efficient. Test that your wrapping didn't break anything. Thsn make that one piece faster. And test again.

Writing single large complex optimized systems only works when the problem is trivial for you.

Answer 2

Your code is incorrect for multiple reasons:

• merge merges the halves of the input array in opposite directions. This does not work as both halves have been sorted in the same direction (increasing or decreasing) so the merge process should proceed from left to right from 0 to mid-1 and from mid to right.
• you always copy from input to output, so you do not merge the sorted halves, but the original halves.
• since you are expected to return a newly allocated array, you probably should not modify the argument array. You should allocate a temporary array for the sorted halves.
• supporting both ascending and descending order seems beyond the scope of your assignment.

Here is a modified version, using a less confusing convention for the upper index: using the index of the element after the last one.

void merge(int *array, int mid, int high, int *temp, bool output_asc) {
    int i = 0;
    int j = mid;
    int k = 0;
    if (output_asc) { //sort ascending
        while (i < mid) {
            if (j >= high || array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }
    } else { //sort descending
        while (i < mid) {
            if (j >= high || array[i] >= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }
    }
    for (i = 0; i < k; i++)
        array[i] = temp[i];
}

void mergesort(int *array, int size, int *temp, bool output_asc) {
    if (size >= 2) {
        int mid = size / 2;
        mergesort(array, mid, temp, output_asc);
        mergesort(array + mid, size - mid, temp + mid, output_asc);
        merge(array, mid, size, temp, output_asc);
    }
}

int *mergesort(int *input, int size) {
    int *output = new int[size];
    int *temp = new int[size];
    for (int i = 0; i < size; i++)
        output[i] = input[i];
    mergesort(output, size, temp, true);
    delete[] temp;
    return output;
}