For some odd reason, I am getting a segmentation fault when I call the merge function. I am using g to compile and have tried passing in different data for the parameters, but I still get this issue.

#include <iostream>
using namespace std;

// Merges two sorted subarrays of A[]. 
// First sorted subarray is A[l..m].
// Second sorted subarray is A[m 1..r].
// You might want to call this function in function mergeSort().
void merge(int A[], int l, int m, int r) {
    int i = 1; //Starting index for left sub array
    int j = m   1; //Starting index for right sub array
    int k = 1; //starting index for temp

    int *temp = new int[r];

    while (i <= m && j <= r) {
        if (A[i] <= A[j]) {
            temp[k] = A[i]; //A[i] is actually smoler than A[j]
            i  ;
            k  ;
        }

        else {
            if (A[i] <= A[j]) {
                temp[k] = A[i]; //A[j] is actually smoler than A[i]
                j  ;
                k  ;
            }
        }

        //Copy all elements from left sbuarray to temp
        while(i<=m){
            temp[k] = A[i];
            i  ;
            k  ;
        }

        //Copy all elements from right subarray to temp
        while(j<=r){
                    temp[k] = A[j];
                    i  ;
                    k  ;
                }

        for(int z =0; z <r; z  ){
            A[z] = temp[z];
        }

    }

}

// using mergeSort to sort sub-array A[l..r]  
// l is for left index and r is right index of the 
// sub-array of A[] to be sorted
void mergeSort(int A[], int l, int r) {
    if (l < r) {
        int middle = l   (r - l) / 2;


        mergeSort(A, l, middle);
        mergeSort(A, middle   1, r);


        merge(A, l, middle, r);
    }
}

int main() {
    cout << "Please enter the length (number of elements) of the input array: ";
    int n;
    cin >> n;

    if (n <= 0) {
        cout << "Illegal input array length!" << endl;
        return 0;
    }

    int *A = new int[n];

    cout << "Please enter each element in the array" << endl;
    cout << "(each element must be an integer within the range of int type)."
            << endl;
    for (int i = 0; i < n; i  ) {
        cout << "A[" << i << "] = ";
        cin >> A[i];
    }

    cout << "Given array A[] is: ";
    for (int i = 0; i < n - 1; i  )
        cout << A[i] << ",";
    cout << A[n - 1] << endl;


    mergeSort(A, 0, n - 1);


    cout << "After mergeSort, sorted array A[] is: ";
    for (int i = 0; i < n - 1; i  )
        cout << A[i] << ",";
    cout << A[n - 1] << endl;

    delete[] A;
    return 0;
}

The merge function is the problem of my program. I have tried debugging and whatnot but cannot determine the problem.

CodePudding user response：

Try using the below code :-

#include<iostream>
using namespace std;
void merge(int arr[],int l,int m,int h)
{
    int n1=m-l 1;
    int n2=h-m;
    int L[n1],M[n2]; 
    for(int i=0;i<n1;i  )
        L[i]=arr[l i];
    for(int i=0;i<n2;i  )
        M[i]=arr[m 1 i];
    int i=0,j=0,k=l;
    while(i<n1&&j<n2)
    {
        if(L[i]<=M[j])
            arr[k  ]=L[i  ];
        else
            arr[k  ]=M[j  ];
    }
    while(i<n1)
        arr[k  ]=L[i  ];
    while(j<n2)
        arr[k  ]=M[j  ];
}
void mergesort(int arr[],int l,int h)
{
    if(l>=h)
        return;
    int m=l (h-l)/2;
    mergesort(arr,l,m);
    mergesort(arr,m 1,h);
    merge(arr,l,m,h);
}
int main()
{
    int n;
    cout<<"Enter the no of element to be sorted:- ";
    cin>>n;
    int arr[1000000];
    for(int i=0;i<n;i  )
        arr[i]=rand();
    mergesort(arr,0,n-1);
    for(int i=0;i<n;i  )
       cout<<arr[i]<<endl;
}

here is the output on online compiler:-

CodePudding user response：

The problem is in this block of code.

while (j <= r) {
  temp[k] = A[j];
  i  ; // Here it should be j   instead of i  
  k  ;
}

You are incrementing i whereas you should increment j. This still produces the wrong output though.

Use debugger to find what's wrong with your code.