-1

I went through the code several times but cant spot any mistake or error. The output is not showing in VS code and on online IDE its saying segmentation fault which i cant understand what it means. I apologize if this is due to any silly mistake but I have wasted a lot of time on this . please help.

#include<iostream>
using namespace std;

void merge_(int a[], int s, int e){
    int mid = (s+e)/2;

    int i = s;
    int j = mid+1;
    int k = s;

    int temp[100];

    while (i<=mid && j<=e)
    {
        if(a[i] < a[j]){
            temp[k++] = a[i++];
        }
        else{
            temp[k++] = a[j++];
        }
    }
    
    while(i<=mid){
        temp[k++] = a[i++];
    }
    
    while(j<=e){
        temp[k++] = a[j++];
    }

    //we need to copy all elements to original arrays
    for (int i = s; i <= e; i++)
    {
        a[i] = temp[i];
    }
    

}

void merge_sort(int a[], int s, int e){
    //base case - 1 or 0 elemnts
    if(s>=e){
        return;
    }

    //follow 3 steps
    //1. Divide
    int mid = (s+e)/2;

    //recursively the arrays - s, mid and mid+1,e
    merge_sort(a,s,mid);
    merge_sort(a,mid-1,e);

    //merge the two parts
    merge_(a,s,e);
}

int main(){

    int a[100];
    int n;
    cin>>n;

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

    merge_sort(a,0,n-1);

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

    
    return 0;
}```
Devesh kumar pandagre
  • 9
  • 1
  • You might find this documentation on using a debugger useful : https://code.visualstudio.com/docs/cpp/cpp-debug. You can then single step through your code, examine all its effects and find the cause of your crash – Pepijn Kramer Oct 17 '22 at 18:05
  • [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – Jesper Juhl Oct 17 '22 at 18:15

2 Answers2

1

I think your problem might come from

merge_sort(a,s,mid);
merge_sort(a,mid-1,e);

The second call always satisfies s < e, so the recursion does not get aborted, also you include a[mid] and a[mid-1] in both divisions.

I believe the following might work

merge_sort(a,s,mid-1);
merge_sort(a,mid,e);

If not, please try to get more information on where the recursion fails

ZwergofPhoenix
  • 141
  • 1
  • 6
1

The problem is coming from this line.

merge_sort(a,mid-1,e)

It is being called with mid being zero. Then s is -1 inside the function. Accessing the array a with an offset of -1 obviously causes a segmentation fault. Did you mean to put mid+1 instead?

Also, next time please add...

cout << "Enter size of list: "; 
cin >> n;

for(int i = 0; i<n; i++){
    cout << "Enter integer element " << i << ": ";
    cin >> a[i];
}

Or even better, temporarily hardcode the array to avoid asking for keyboard input altogether.

I understand its unfinished, but sharing code that asks for keyboard input without any prompt whatsoever is hella confusing.

MarshallBS
  • 76
  • 6
  • Thanks it worked with `mid+1` and sorry I didn't think about others perspective. – Devesh kumar pandagre Oct 18 '22 at 12:41
  • You're welcome. Another tip when you're debugging low-level algorithmic code like this is to *always* add checks on the index bounds before you access an array. Add `if ( 100 <= s || s < 0 ) { cout << "array index out of bounds"; return; }`. Only remove the bounds checking ( for optimal speed ) *after* you've thoroughly tested the code with all kinds of input. – MarshallBS Oct 18 '22 at 20:17