Merge sort logic failure in allocating memory.

Question

I am working on an implementation of merge-sort which will sort a list of songs by their length. I have written the following and have been unable to fins the flaw in my logic. Instead of returning a sorted list these functions return a list of one item from the middle of the original list.

vector<song> merge( vector<song> firstList, vector<song> secondList){
 vector<song> outPut;
 int i = 0; int n = 0;
 while( outPut.size() < (firstList.size() + secondList.size()-1 )){
    if( firstList[i].length < secondList[n].length){
        outPut.push_back( firstList[i]);
        i++;
    }else{
        outPut.push_back( secondList[n]);
        n++;
    }
 }
return outPut;
}
vector<song> mergeSortLength( vector<song> playlist){
 int scope = playlist.size()/2;
 vector<song> firstHalf( &playlist[0], &playlist[scope]);
 vector<song> secondHalf( &playlist[scope], &playlist[playlist.size()]);
 if ( firstHalf.size() != 1){
    firstHalf = mergeSortLength(firstHalf);
 }
 if ( secondHalf.size() != 1){
    secondHalf = mergeSortLength( secondHalf);
 }
 return merge( firstHalf, secondHalf);
}

If I change the while loop condition from

( outPut.size() < (firstList.size() + secondList.size() -1)){

to

( outPut.size() < (firstList.size() + secondList.size())){

it gets about halfway though the list sorting successfully until the compiler spits out:

playList(27898,0x7fff78b7b000) malloc: * mach_vm_map(size=7526769998340063232) failed (error code=3) * error: can't allocate region *** set a breakpoint in malloc_error_break to debug libc++abi.dylib: terminating with uncaught exception of type std::bad_alloc: std::bad_alloc Abort trap: 6

I really appreciate anyones help. My eyes are going fuzzy from staring at this.

Compare your code with [the merge sort implemented here](http://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c) — PaulMcKenzie, Jun 02 '16 at 21:31
And here is a [small test](http://ideone.com/L11iM6). I suggest you take the code you see at the link, take your code, and carefully debug where your code fails and where the good example does not fail. It looks like you're trying to imitate `std::inplace_merge`, and you're getting it wrong. [Here is another link](http://en.cppreference.com/w/cpp/algorithm/inplace_merge) with an example. — PaulMcKenzie, Jun 02 '16 at 21:39
Thank you for the tip. I'll compare and I'll let you know if it helps. — Daniel Quinn, Jun 02 '16 at 21:56
Any reason you don't just implement song::operator<() to compare length, and call std::stable_sort()? — Wheezil, Jun 03 '16 at 03:41

score 0 · Answer 1 · answered Jun 03 '16 at 00:28

0

I didn't see with a lot of attention, but maybe you want

vector<song> secondHalf( &playlist[scope+1], &playlist[playlist.size()-1]);

the &playlist[playlist.size()] without -1 I think is the source of your problem, but I have not tried.

answered Jun 03 '16 at 00:28

ruirodrigues1971__

332
1
6

The -1 avoids a malloc error because it stops me from accessing memory past the end of the vector. The drawback is when firstList and/or secondList has a size of 1. This causes the functions to return a list of one element. To be fair, that list is sorted. See rcgldr's comment who really did the heavy lifting. – Daniel Quinn Jun 05 '16 at 02:32

rcgldr · Accepted Answer · 2016-06-04T16:42:52.000

In merge(), the code doesn't check to see if the end of a vector has been reached, specifically, if i >= firstList.size() or n >= secondList.size(), in which case the remainder of the other vector would be copied. The while statement should not have the -1 near the end.

VS complains about the temp vector creation using &playlist[playlist.size()], since the subscript is out of range. An optional way to do this is to use begin() + index, which is an iterator:

    vector<song> firstHalf( playlist.begin()+0, playlist.begin()+scope);
    vector<song> secondHalf( playlist.begin()+scope, 
                 playlist.begin()+playlist.size());

It's been over a day, so posting a fixed version in case anyone is interested. All that vector creation and push backs add a lot of overhead, it would have been better to do a one time allocation, and then just use iterators or indices to deal with the sub-vectors.

vector<song> merge( vector<song> firstList, vector<song> secondList){
    vector<song> outPut;
    size_t i = 0; size_t n = 0;
    while( outPut.size() < (firstList.size() + secondList.size()) ){
        if( firstList[i].length < secondList[n].length){
            outPut.push_back( firstList[i]);
            if(++i >= firstList.size()){
                do
                    outPut.push_back( secondList[n]);
                while(++n < secondList.size());
                break;
            }
        }else{
            outPut.push_back( secondList[n]);
            if(++n >= secondList.size()){
                do
                    outPut.push_back( firstList[i]);
                while(++i < firstList.size());
                break;
            }
        }
    }
    return outPut;
}

vector<song> mergeSortLength( vector<song> playlist){
    size_t scope = playlist.size()/2;
    vector<song> firstHalf( playlist.begin()+0, playlist.begin()+scope);
    vector<song> secondHalf( playlist.begin()+scope, playlist.begin()+playlist.size());
    if ( firstHalf.size() != 1){
        firstHalf = mergeSortLength(firstHalf);
    }
    if ( secondHalf.size() != 1){
        secondHalf = mergeSortLength( secondHalf);
    }
    return merge( firstHalf, secondHalf);
}

You are absolutely correct! Thank you. This explains quite a lot to me and I really appreciate how thorough you were. — Daniel Quinn, Jun 05 '16 at 02:39

Merge sort logic failure in allocating memory.

2 Answers2