Midpoint of Open-Ended Interval for Merge Sort

Question

According to my algorithms book, this closed interval version of merge sort is properly implemented, which it is. However, I'd like to setup an open-ended interval version of this sort algorithm. What's the proper way to do this? Here's my current closed interval code:

#include <iostream>
using namespace std;

template<typename T>
void mergeHalf(T *src, uint start, uint mid, uint end)
{
    T *temp = new T[end + 1];

    uint lhs = start, rhs = mid + 1;
    uint index = start;

    while(lhs <= mid && rhs <= end)
    {
        if(src[lhs] <= src[rhs])
            temp[index] = src[lhs++];
        else
            temp[index] = src[rhs++];

        index++;
    }

    while(lhs <= mid)
        temp[index++] = src[lhs++];

    while(rhs <= end)
        temp[index++] = src[rhs++];

    for(index = start; index <= end; ++index)
        src[index] = temp[index];

    delete [] temp;
}

template<typename T>
void merge(T *src, uint start, uint end)
{
    if(start < end)
    {
        // Add one to midpoint to even out size division
        const uint m = start + (end - start) / 2;

        merge(src, start, m);
        merge(src, m + 1, end);
        mergeHalf(src, start, m, end);
    }
}

int main()
{
    const size_t n = 6;
    int myArray[n] = {5, 2, 3, 1, 7, 9};
    merge(myArray, 0, n - 1);

    for(size_t i = 0; i < n; ++i)
        cout << myArray[i] << ' ';
    cout << endl;

    return 0;
}

I'm trying to alter this merge sort algorithm to work with an open ended range, i.e. calling merge(myArray, 0, n); instead of merge(myArray, 0, n - 1);

EDIT: As of now, something is wrong with the midpoint recursion when I'm passing in the size of the array and altering the loops to be open ended (non-inclusive). I've been trying to track the problem, but I can't see it at all.

Thanks for reading, any help is greatly appreciated; also, any language listed in the tags is okay. This algorithm is implemented in C++11 with GCC 4.9.2.

Here's a block of code, make it open ended. That in itself is too open ended of a question. Please be more specific. — Malik Brahimi, Feb 22 '15 at 15:47
Basically, I'm trying to pass in the size of the array as end, instead of the last index of the array. — kevr91, Feb 22 '15 at 15:51
I don't really understand the objective but you should at least know that the size of an array is exactly one more than the last index. — Malik Brahimi, Feb 22 '15 at 15:58
Sorry, Malik, I don't know how to further explain it. I added a bit more explanation. — kevr91, Feb 22 '15 at 16:11
The original program doesn't work because this line has the wrong end test: `for(index = start; index < end; ++index)`. I don't know what problem you're having with the recursion after converting to open-ended, but the most likely is stack overflow because the recursion test should be condition needs to change to `if (end - start > 1)`, which matches the original end test (recurse if there is more than one element to sort). No comment on the rest of the code. — rici, Feb 22 '15 at 16:22
Ah, indeed, I was editing back to original to show you guys, forgot to fix the copy loop. Apologies. Also, your solution seems to make sense, I'll try it out. Thank you, rici. — kevr91, Feb 22 '15 at 16:24

score 0 · Answer 1 · edited May 23 '17 at 12:12

For "open ended", you use mid instead of mid+1, and you check for < high index instead of <= high index.

In this thread are examples of somewhat optimized top down and bottom up merge sorts, both of them "open ended". Both examples are passed a second array to use for the merge sort (as opposed to the top down approach that dynamically allocates, copies, and frees sub-arrays, which is significantly slower).

merge_sort using vectors works well with less than 9 inputs

Midpoint of Open-Ended Interval for Merge Sort

1 Answers1