Segmentation fault in merge sort code

Question

I have written this merge sort program in c++ but I am getting "Segmentation fault (core dumped)" error after running the code. Even though there is no compilation error. Can you please tell me what's the mistake I am doing? While taking input in the array it is showing that error. If I change it to push_back, the input is fine but later in merge function, it is showing the same error.

//merging 2 sorted subarrays.
#include <iostream>
#include <vector>
using namespace std;

void merge(vector <int> &a,vector <int> &b,vector <int> &c)
{
    int i=0,j=0,k=0,bL=b.size(),cL=c.size();
    while(i<bL && j<cL)
    {
        if(b[i]<c[j])
        {
            a[k]=b[i];
            i++;k++;
        }
        else
        {
            a[k]=c[j];
            j++;k++;
        }
    }
    while(i<bL)
    {
        a[k]=b[i];
        i++;k++;
    }
    while(j<cL)
    {
        a[k]=c[j];
        j++;k++;
    }
    cout<<"array a inside merge is: "<<endl;
    for(int p=0;p<a.size();p++)
    {
        cout<<a[p]<<endl;
    }

}
void mergeSort(vector <int> &a)
{
    vector <int> l, r;
    int mid;
    if(a.size()<2) return;

    mid = a.size()/2;
    for(int i=0;i<mid;i++)
    {
        l[i]=a[i];
    }
    for(int i=mid;i<a.size();i++)
    {
        r[i-mid]=a[i];
    }
    mergeSort(l);
    mergeSort(r);
    merge(a, l, r);
}
int main()
{
    int n;
    vector <int> a;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    mergeSort(a);
    for(int p=0;p<n;p++)
    {
        cout<<a[p]<<endl;
    }
    return 0;
}

1) "_Even though there is no compilation error._" If the code compiles - it doesn't mean that it runs correctly. 2) `cin>>a[i];` is undefined behavior, when `a` is empty. 3) "_If I change it to push_back, the input is fine but later in merge function, it is showing the same error_" Then, your merge function has some sort of undefined behavior. Did you try stepping through your code with a debugger? — Algirdas Preidžius, May 08 '18 at 14:28
@AlgirdasPreidžius No, I didn't go through any debugger, but what can I use in place of a[ i ] while taking input? and also, in merge function error is in this syntax only. — Saurav Bhagat, May 08 '18 at 14:30
`vector`s don't expand automatically if you assign to elements that don't exist. — molbdnilo, May 08 '18 at 14:30
Use `push_back` or tell the vector how many elements when you construct it. There will be another probelm inside the merge sort though from what you've said. — doctorlove, May 08 '18 at 14:32
Read about [`vector::push_back`](http://en.cppreference.com/w/cpp/container/vector/push_back) in your favourite C++ book. If you don't have one, find inspiration [here](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). (If you're following some kind of course or book, this should have been mentioned by the time you get to sorting.) — molbdnilo, May 08 '18 at 14:32

doctorlove · Answer 1 · 2018-05-09T08:39:24.717

1

Whever you access an element in a vector using [] you might get a seg fault. This code,

vector <int> a;

gives you an empty vector.

Asking for a[0] won't work if there's nothing in a yet. Trying to set a[0] to a value won't work either. It doesn't exist. Yet.

You have a similar problem in mergeSort when you use

vector <int> l, r;

These are also empty vectors.

You can use push_back (or even emplace_back) to add new elements. Or use a constructor overload to state how many elements you want. For example,

vector <int> a(10);

gives you a vector of ten ints, so a[0] is fine to read from or write to. a[11] isn't.

Practise using a vector first then try your merge sort.

edited May 09 '18 at 08:39

answered May 08 '18 at 14:45

doctorlove

18,872
2
46
62

but I'm not asking for a[ 0 ], Instead, I am taking input in that position? So, even though it'll not work? Also, push_back won't work inside merge as I have to start from 0 everytime, so if i'll push , it will not overwrite. – Saurav Bhagat May 08 '18 at 14:50
I'll be more explicit - you are trying to put something in index 0. But there's no space for it. – doctorlove May 08 '18 at 14:51

tegginamaniss · Answer 2 · 2018-05-08T14:58:33.800

0

The reason for getting a segmentation fault is you access the location of the memory which does not exist (more accurate to say as not allocated). Say you have a vector of length 3 and you try to access 4th position, you get a segmentation fault.

As opposed to @doctorlove's answer, I would say it is possible to use []. However, you need the following implementation (only shown for main(), please implement with the same logic in the other functions). See the documentation of std::vector for more info.

int main()
{
    size_t n;

    std::cin >> n;
    std::vector <int> a(n);

    for(int i=0;i<n;++i)
    {
        std::cin >> a[i];
    }

    // mergeSort(a);

    for(int i=0;i<n;++i)
    {
        std::cout << a[i] << "\n";
    }
    return 0;
}

Hope this helps. Cheers.

edited May 08 '18 at 14:58

answered May 08 '18 at 14:53

tegginamaniss

151
10

also note the use of `++i` instead of `i++`. Pre-increment and post-increment matter. – tegginamaniss May 08 '18 at 14:54
Thanks, but I tried doing this, Input is getting correct but again same error is coming inside some function, I applied this in all vector declarations. – Saurav Bhagat May 08 '18 at 14:59
Bear in mind you might not get a seg fault in general. It's undefined bahaviour to access inavlid memory – doctorlove May 08 '18 at 15:01
This is something you can figure out with debugging. Try commenting and uncommenting parts of your code, step by step in each function. This way you will know where exactly you hit the segmentation fault. That is how I did it for `main()`. And I believe I have given sufficient answer for you to figure out the full solution from the main answer. – tegginamaniss May 08 '18 at 15:05

score 0 · Answer 3 · answered May 08 '18 at 15:09

here is the final code after changes:

//merging 2 sorted subarrays.
#include <iostream>
#include <vector>
using namespace std;

void merge(vector <int> &a,vector <int> &b,vector <int> &c)
{
    int i=0,j=0,k=0,bL=b.size(),cL=c.size();
    while(i<bL && j<cL)
    {
      if(b[i]<c[j])
      {
        a[k]=b[i];
        i++;k++;
      }
      else
      {
        a[k]=c[j];
        j++;k++;
      }
    }
    while(i<bL)
    {
      a[k]=b[i];
      i++;k++;
    }
    while(j<cL)
    {
      a[k]=c[j];
      j++;k++;
    }
    cout<<"array a inside merge is: "<<endl;
    for(int p=0;p<a.size();p++)
    {
      cout<<a[p]<<endl;
    }

}
void mergeSort(vector <int> &a)
{
    vector <int> l, r;
    int mid;
    if(a.size()<2) return;

    mid = a.size()/2;
    for(int i=0;i<mid;i++)
    {
      l.push_back(a[i]);
    }

    //change2
    for(int i=0;i<a.size()-mid;i++)
    {
      r.push_back(a[mid+i]);
    }
    mergeSort(l);
    mergeSort(r);
    merge(a, l, r);
}
int main()
{
    int n;
    cin>>n;

    //change1
    vector <int> a(n);
    for(int i=0;i<n;i++)
    {
      cin>>a[i];
    }
    mergeSort(a);
    cout<<"Final array is:"<<endl;
    for(int p=0;p<n;p++)
    {
      cout<<a[p]<<endl;
    }
    return 0;
}

Expected results will be the parts of the array on which the merge function is currently working. Through numerous iterations, it will finally converge to form the sorted array! — Rajat Gupta, May 09 '18 at 20:28

Segmentation fault in merge sort code

3 Answers3