Merge Sort | C++ - Segmentation Fault

Question

I thought I'd revise my concepts by coding some basic DS and Algos. After a great pace, I am kinda stuck now and not being able to identify my mistake. I am getting a Segmentation Fault in the below code result. Any help would be great!

#include<bits/stdc++.h>
using namespace std;

void merge(int *arr, int s, int m, int e){
    int n1 = m-s, n2 = e-m+1;
    int L[n1], R[n2];
    for(int i=0; i<n1; i++)
        L[i] = arr[s+i];
    for(int i=0; i<n2; i++)
        R[i] = arr[m+i];
    
    int p1 = 0, p2 = 0, k = s;
    while(p1<n1 && p2<n1){
        if(L[p1] <= R[p2])
            arr[k++] = L[p1++];
        else
            arr[k++] = R[p2++];
    }

    while(p1<n1)
        arr[k++] = L[p1++];
    while(p2<n2)
        arr[k++] = R[p2++];
    return;
}


void mergeSort(int *arr, int s, int e){
    if(s>=e) return;
    int m = (s+e)/2;
    mergeSort(arr, s, m-1);
    mergeSort(arr, m, e);
    merge(arr, s, m, e);
    return;
}
int main(){
    int n;
    cin>>n;
    int arr[n];
    for(int i=0; i<n; i++)
        cin>>arr[i];
    mergeSort(arr, 0, n-1);

    for(int i=0; i<n; i++)
        cout<<arr[i]<<" ";
    cout<<endl;

    return 0;
}

Thanks in advance!

The best help would be your debugger, it would point you precisely where the fault occurs and you will be able to examine values of all variables at that moment. I'm afraid I cannot read your code, because I have no slightest idea what each of these one-letter variables means. — Yksisarvinen, Aug 27 '20 at 14:13
**Recommended reading:** [Why should I not #include ?](https://stackoverflow.com/q/31816095/560648) — Asteroids With Wings, Aug 27 '20 at 14:17
... and [Why aren't variable-length arrays part of the C++ standard?](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard) and [Why is `using namespace std;` considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Ted Lyngmo, Aug 27 '20 at 14:18
It's actually easier to avoid off-by-one errors if you stick to the conventional half-open intervals. — molbdnilo, Aug 27 '20 at 14:30
That will crash if the input is large enough due to your use of arrays. Use `std::vector`. — molbdnilo, Aug 27 '20 at 14:35
@TedLyngmo Look to your right! [New post formatting on Meta.SE](https://meta.stackexchange.com/questions/353446/new-post-formatting?cb=1). — Asteroids With Wings, Aug 27 '20 at 14:38
@Ted Yes it is :( Facebook's done a similar thing. It's like everybody has forgotten basic design principles. Or was it just not taught to the "new" generation? — Asteroids With Wings, Aug 27 '20 at 14:39
I was getting an off-by-one error, I was trying to fetch the wrong index value in my array. Switched back to the conventional intervals to divide the array s->m & m+1->e — Rahul Sharma, Aug 27 '20 at 14:40
@AsteroidsWithWings Yeah, I switched to the old FB look and wrote a long comment about _why_ I did it. Fat chance anyone listens... :) — Ted Lyngmo, Aug 27 '20 at 14:41
@RahulSharma You're getting a stackoverflow. Did you manage to fix it? I converted your code to standard C++ and used the `vector`s `at()` function to catch any errors in your indexing. This makes debugging simpler: https://pastebin.com/R74nZ4ew — Ted Lyngmo, Aug 27 '20 at 14:44
FYI, professional coding guidelines say to always use `{` and `}` for `if`, `while`, `for`, `else` and `do-while`. This will free you from some common, but hard to find, run-time defects. — Thomas Matthews, Aug 27 '20 at 15:10

score 1 · Accepted Answer · answered Aug 27 '20 at 16:23

The segmentation error is because you have an infinite recursion loop. There were some problems with the indices and one typo where you meant n2 but wrote n1.

#include <iostream>

using namespace std;

void merge(int *arr, int s, int m, int e){
    int n1 = m-s+1, n2 = e-m;
    int L[n1], R[n2];

    for(int i=0; i<n1; i++)
        L[i] = arr[s+i];
    for(int i=0; i<n2; i++)
        R[i] = arr[m+i+1];

    int p1 = 0, p2 = 0, k = s;
    while(p1<n1 && p2<n2){
        if(L[p1] <= R[p2])
            arr[k++] = L[p1++];
        else
            arr[k++] = R[p2++];
    }

    while(p1<n1)
        arr[k++] = L[p1++];
    while(p2<n2)
        arr[k++] = R[p2++];
    return;
}

void mergeSort(int *arr, int s, int e){
    if(s>=e) return;
    int m = (s+e)/2;
    mergeSort(arr, s, m);
    mergeSort(arr, m+1, e);
    merge(arr, s, m, e);
    return;
}

int main() {
    int n;

    cout << "Select value for N:";
    cin>>n;
    int arr[n];

    cout << "Reading input:";
    for(int i=0; i<n; i++)
        cin >> arr[i];

    cout << "Your input is:" << endl;
    for(int i=0; i<n; i++)
        cout << arr[i]<<" ";
    cout << endl;

    cout << "Running merge sort" << endl;
    mergeSort(arr, 0, n-1);

    cout << "Final array:" << endl;
    for(int i=0; i<n; i++)
        cout<<arr[i]<<" ";
    cout << endl;

    return 0;
}

Merge Sort | C++ - Segmentation Fault

1 Answers1