CODEWITHSUNDEEP
c++arraysalgorithmsortingmergesort
big_zhicheng
big_zhicheng

Reputation: 23

Runtime error of C++ implementation of merge sort

So I was working on the problems on Leetcode, 912. This is an as simple as it can be problem-- sort an array in ascending order. I am just doing it to go over all the sorting algorithms. However, when it come to merge sort, I wrote this algorithm and it shows a run time error as shown below. Some simple test cases with 6 or 10 integers in it passed. but an run time error occurs when it comes to a much longer test case. Any one have an idea of what part of my code might cause this? Many thanks in advance!

void mergesort(vector <int> &nums) {
    int length=nums.size();
    if (length<2)
    {
        return ;
    }
    int mid= length/2;
    vector <int> left;
    vector <int> right;
    for (int x=0;x<mid;x++)
    {
        left.push_back(nums[x]);
    }
    for (int y=0;y<length-mid;y++)
    {
        right.push_back(nums[y+mid]);
    }
    mergesort(left);
    mergesort(right);
    merge(left,right,nums);

}
void merge(vector <int>& left,vector <int>& right,vector <int>& nums){
    int i,j,count {0};
    int l1=left.size();
    int l2=right.size();
        while (i<l1&&j<l2)
        {
            if (left[i]<right[j])
            {
                nums[count]=left[i];
                count++;
                i++;
            }
            else
            {
                nums[count]=right[j];
                count++;
                j++;
            }
        }
        while (i<l1)
        {
            nums[count]=left[i];
            count++;
            i++;
        }
        while (j<l2)
        {
            nums[count]=right[j];
            count++;
            j++;
        }
}
vector<int> sortArray(vector<int>& nums){
    mergesort(nums);
    return nums;
}

I passed test case like :[5,2,3,1] but for a much much longer vector input: I got run time error message: AddressSanitizer: SEGV on unknown address 0x61eff7f80674 (pc 0x000000418d91 bp 0x7fff0f0847c0 sp 0x7fff0f0845a0 T0)

Upvotes: 1

Views: 169

Answers (1)

Mike Vine
Mike Vine

Reputation: 9837

You do not initialize either i or j:

 int i,j,count {0};

This will only initialize count to 0. Turn up or actually read your compiler warnings as it will tell you this.

Change this to:

int i{0};
int j{0};
int count{0};

Upvotes: 2

Related Questions