C++ Merge Sort getting garbage element

  array-merge, c++, mergesort

Our instructor asked us to create our own Merge Sort Algorithm before showing us how to make one. He explained how it works and this is what I came up. It works but there is a bug, my code catches garbage number. First garbage number occurs at vector/array size is 7 then next is 11 and so on.
Output of this code is:

Size of Vec1: 7
Size of Vec2: 8
1 3 4 5 6 15 16 0
#include <iostream>
#include <vector>

std::vector<int> merge(std::vector<int> left, std::vector<int> right);

std::vector<int> mergeSort(std::vector<int> &vec){

    if(vec.size() <= 1){
    return vec;
    }
    
    int halfsize = vec.size() / 2;
    
    std::vector<int> left (vec.begin(), vec.begin() + halfsize);
    std::vector<int> right(vec.begin() + halfsize, vec.end());
    return merge(mergeSort(left), mergeSort(right));

}

std::vector<int> merge(std::vector<int> left, std::vector<int> right){
    std::vector<int> newVector;
    size_t leftCurrent = 0;
    size_t rightCurrent = 0;
    
    while(newVector.size() <= right.size() + left.size()){
        //compare left and right current number
        if(right[rightCurrent] < left[leftCurrent]){
            newVector.push_back(right[rightCurrent]);
            rightCurrent++;
            //if all element in right is added
            if(rightCurrent >= right.size()){
                //while all element in left is not added, add each element
                while(leftCurrent + 1 <= left.size()){
                    newVector.push_back(left[leftCurrent]);
                    leftCurrent++;
                }
                return newVector;
            }
        }
        else{
            newVector.push_back(left[leftCurrent]);
            leftCurrent++;
            //if all element in left is added
            if(leftCurrent >= left.size()){
                //while all element in right is not added, add each element
                while(rightCurrent + 1 <= left.size()){
                    newVector.push_back(right[rightCurrent]);
                    rightCurrent++;
                }
                return newVector;
            }
        }
    }
    
    return newVector;
}

int main(){
    
    std::vector<int> vec1 {6,5,3,1,8,7,2,4,9,10,11};
    std::cout << "Size of Vec1: " << vec1.size() << std::endl;
    
    std::vector<int> vec2 = mergeSort(vec1);
    std::cout << "Size of Vec2: " << vec2.size() << std::endl;
    
    for(auto& i: vec2){
        std::cout << i << " ";
    }
    std::cout << std::endl;
    return 0;
}

Source: Windows Questions C++

LEAVE A COMMENT