CODEWITHSUNDEEP
c++algorithmsortingmergesort
brett
brett

Reputation: 5649

Why am I getting vector subscript out of range error in the Merge Sort?

void merge(vector<int> dst,vector<int> first,vector<int> second)
{
    int i=0,j=0;

    while(i<first.size()&&j<second.size())
    {
        if(first[i]<second[j])
        {
            dst.push_back(first[i]);
            i++;
        }
        else
        {
            dst.push_back(second[j]);
            j++;
        }
    }
    while(i<first.size()
    dst.push_back(first[i++]);

    while(j<second.size())
    dst.push_back(second[j++]);
}

void mergeSort(vector<int> &a)
{   
    size_t sz = a.size();
    cin.get();
    if(sz>1)
    {   
        vector<int> first(&a[0],&a[sz/2]);
        vector<int> second(&a[(sz/2)+1],&a[sz-1]);

        mergeSort(first);
        mergeSort(second);

        merge(a,first,second);  
    }
}

void MergeSort(int* a,size_t size)
{
   vector<int> s(&a[0],&a[size-1]);
   mergeSort(s);
}

Can some one help me what is the problem with this code ? I am getting vector subscript outof range error.

Upvotes: 0

Views: 521

Answers (3)

Loki Astari
Loki Astari

Reputation: 264361

Your sub vectors are specified incorrectly.
Remember the iterators specify the beginning to one past the end.

So this will misses the middle element and the last element in the vector.
And is also undefined for really short vectors of length 2

    vector<int> first(&a[0],&a[sz/2]);
    vector<int> second(&a[(sz/2)+1],&a[sz-1]);

Imagine if a is the vector { A, B, C, D}

    first:  {A,B}   0 -> 2 (where 2 is one past the end so index 0 and 1_
    second: {}      3 -> 3 (Since one past the end equals the start it is empty}

Or Try a bigger vector: { A, B, C, D, E, F, G, H, I}

    first:  {A, B, C, D}    0 -> 4 (4 is one past the end so index 0,1,2,3)
    second: {F, G, H}       5 -> 8 (8 is one past the end so index 5,6,7)

Or Try a smaller vector: { A, B}

    first:  {A}    0 -> 1
    second: {BANG} 2 -> 1

Should be:

    int* st = &a[0];
    // Using pointer arithmatic because it was too late at night
    // to work out if &a[sz] is actually legal or not.
    vector<int> first (st,      st+sz/2]); // sz/2 Is one past the end.
    vector<int> second(st+sz/2, st+sz   ); // First element is sz/2  
                                           // one past the end is sz

The vectors passed into merge(). The dst parameter has to be passed by reference as it is an out parameter. But also note that first and second parameters are const so we can pass by const reference (to avoid the copy step).

void merge(vector<int>& dst,vector<int> const& first,vector<int> const& second)

Also the merge function:

Is pushing the value into dst. But dst is already full from the data that came in. So before we do the merge the destination must be cleared.

    mergeSort(first);
    mergeSort(second);

    // Must clear a before we start pushing stuff into.
    a.clear();   // Add this line.
    merge(a,first,second);

Upvotes: 2

Torres
Torres

Reputation: 5400

Martin is right, the problem is the contructor of the auxiliar vectors:

Original vector: 1 9 7 9 2 7 2 1 9 8

iter1: 2, iter2: 8

   vector<int> v( iter1, iter2 ); //new vector: 2 7 2 1 9

http://www.cppreference.com/wiki/stl/vector/vector_constructors

And talking about merge-sort and other sorting algorithms, I´ve found a very useful web:

http://www.sorting-algorithms.com/merge-sort

Upvotes: 0

Will A
Will A

Reputation: 24988

If sz == 2, &a[(sz/2)+1] will try to take the address of a[2], which will give you this error.

Upvotes: 3

Related Questions