problem with merge sort

Question

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.

Answer 1

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

Answer 2

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);  

Answer 3

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