Targeting failure in Mergesort

Question

I tried to recreate the Mergesort algorithm in C++, but when compiling, the error "segmentation fault" appears. Here is the code below. What could I be doing wrong?

#include <iostream>
using namespace std;
void merge (int *arr, int lo, int m, int hi){
    int n1, n2;
    n1 = m - lo + 1; //maximo do subarray1
    n2 = hi - m; //maximo do subarray2
    int *L, *R, i, j, k;
    for(i=lo; i<n1; i++){
        L[i]=arr[lo+i]; //cria array temporario para armazenar uma subarray 
    } //obs: vai de lo ateh n1-1
    for (j = hi; j< n2; j++){
    R[j]=arr[m+1+j]; //cria array temporario para armazenar outra subarray
    }// obs vai de m+1 ateh n2-1
    i=0;
    j=0;
    k=lo; // comparar os subarrays e preencher o arr com os menores elementos de cada sub por vez
    while (i<n1 && j<n2){
        if (L[i]<=R[j]){
            arr[k]=L[i]; //se o de L for menor, arr recebe de L
            i++;
        }
        else {
            arr[k]=R[j]; //se o de R for menor, arr recebe de R
            j++;
        }
        k++; //vai preenchendo arr[k]
    }
    while (i<n1){ // termina de preencher arr com o q falta de L
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j<n2){ // termina de preencher arr com o q falta de R
        arr[k] = R[j];
        j++;
        k++;
        }
    }
    void mergesort(int *arr, int lo, int hi){ //dividir e conquistar
        if (lo < hi){
            int m;
            m = (hi + lo)/2;
            mergesort (arr, lo, m);
            mergesort (arr, m+1, hi);
            merge (arr, lo, m, hi);
            }
   }
void printarr(int *arr){ //imprime array ordenado
    for (int i=0; i<sizeof(arr)/sizeof(arr[0]); i++){
        cout << arr[i] << " ";
        }
    }
int main() {
int *vetor, N;
cin >> N;
for (int i = 0; i<N; i++){
    cin >> vetor[i];
}
mergesort(vetor, 0, N);
printarr(vetor);
return 0;
}

Answer 1

The main reason is not initialize memory for the vectors. I did using malloc() even though it is from C, after all it is already using several things that should only be used in C same.

I fixed some more problems and organize the code. If the code needs comment it is because it is too confused.

There are other problems in the algorithm, it is not doing carto, but at least there is more error described in the question.

#include <iostream>
using namespace std;
void merge(int *arr, int lo, int m, int hi) {
    int n1 = m - lo + 1; //maximo do subarray1
    int n2 = hi - m; //maximo do subarray2
    int *L = (int*)malloc(sizeof(int) * n1);
    int *R = (int*)malloc(sizeof(int) * n2);
    for (int i = lo; i < n1; i++) {
        L[i] = arr[lo + i]; //cria array temporario para armazenar uma subarray 
    } //obs: vai de lo ateh n1-1
    for (int j = hi; j < n2; j++) {
        R[j] = arr[m + 1 + j]; //cria array temporario para armazenar outra subarray
    }// obs vai de m+1 ateh n2-1
    int i = 0;
    int j = 0;
    int k = lo; // comparar os subarrays e preencher o arr com os menores elementos de cada sub por vez
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i]; //se o de L for menor, arr recebe de L
            i++;
        } else {
            arr[k] = R[j++]; //se o de R for menor, arr recebe de R
        }
        k++; //vai preenchendo arr[k]
    }
    while (i<n1){ // termina de preencher arr com o q falta de L
        arr[k++] = L[i++];
    }
    while (j < n2) { // termina de preencher arr com o q falta de R
        arr[k++] = R[j++];
    }
}
void mergesort(int *arr, int lo, int hi) { //dividir e conquistar
    if (lo < hi) {
        int m = (hi + lo) / 2;
        mergesort(arr, lo, m);
        mergesort(arr, m + 1, hi);
        merge(arr, lo, m, hi);
    }
}
void printarr(int *arr, size_t size){ //imprime array ordenado
    for (int i = 0; i < size; i++){
        cout << arr[i] << " ";
    }
}
int main() {
    int N;
    cin >> N;
    int *vetor = (int *)malloc(sizeof(int) * N);
    for (int i = 0; i < N; i++) {
        cin >> vetor[i];
    }
    mergesort(vetor, 0, N);
    printarr(vetor, N);
}

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.

Answer 2

Thank you, here’s the corrected code:

#include <iostream>
using namespace std;
void merge(int *arr, int lo, int m, int hi) {
int n1 = m - lo + 1; //maximo do subarray1
int n2 = hi - m; //maximo do subarray2
int L[n1];
int R[n2];
for (int i = 0; i < n1; i++) {
    L[i] = arr[lo + i]; //cria array temporario para armazenar uma subarray 
} //obs: vai de lo ateh n1-1
for (int j = 0; j < n2; j++) {
    R[j] = arr[m + 1 + j]; //cria array temporario para armazenar outra subarray
}// obs vai de m+1 ateh n2-1
int i = 0;
int j = 0;
int k = lo; // comparar os subarrays e preencher o arr com os menores elementos de cada sub por vez
while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
        arr[k] = L[i]; //se o de L for menor, arr recebe de L
        i++;
    } else {
        arr[k] = R[j++]; //se o de R for menor, arr recebe de R
    }
    k++; //vai preenchendo arr[k]
}
while (i<n1){ // termina de preencher arr com o q falta de L
    arr[k++] = L[i++];
}
while (j < n2) { // termina de preencher arr com o q falta de R
    arr[k++] = R[j++];
}
}
void mergesort(int *arr, int lo, int hi) { //dividir e conquistar
if (lo < hi) {
    int m = (hi + lo) / 2;
    mergesort(arr, lo, m);
    mergesort(arr, m + 1, hi);
    merge(arr, lo, m, hi);
}
}
void printarr(int *arr, size_t size){ //imprime array ordenado
for (int i = 0; i < size; i++){
    cout << arr[i] << " ";
}
}
int main() {
int N;
cin >> N;
int vetor[N];
for (int i = 0; i < N; i++) {
    cin >> vetor[i];
}
mergesort(vetor, 0, N);
printarr(vetor, N);
}