Recibo un error de segmentación al implementar mergesort. He comprobado que la matriz está fuera de los límites. Me encantaría recibir ayuda para averiguar dónde me he equivocado. He probado las entradas para matrices pequeñas, como las de tamaño 10, donde he tomado el tamaño de la temperatura como estático (> 10). Llevo horas tirando de mi cabello.

ACTUALIZACIÓN: Solo necesitaba cambiar mid = (low + high) / 2.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void merges(int arr[],int low,int mid,int high)
{
    int i=low,j=mid+1,k=0;
    int temp[high-low+1];
    while(i<=mid && j<=high)
    {
           if(arr[i]<arr[j])
            {
                temp[k++]=arr[i];
                i++;
            }
            else
            {
                temp[k++]=arr[j];
                j++;               
            }
    }
    if(i>mid)
    {
        while(j<=high)
        {
            temp[k++]=arr[j];
            j++;
        }
    }
    else
    {
        while(i<=mid)
        {
            temp[k++]=arr[i];
            i++;
        }
    }
    j=0;
    for(i=low;i<=high;i++)
    {
        arr[i]=temp[j++];    
    }
}

void mergesort(int arr[],int low,int high)
{
    if(low<high)
    {
    int mid=low+high/2;
    mergesort(arr,low,mid);
    mergesort(arr,mid+1,high);
    merges(arr,low,mid,high);
    }   
}

int main(){
    int n;
    cin >> n;
    int arr[n];
    for(int arr_i = 0;arr_i < n;arr_i++){
    cin >> arr[arr_i];
    }
    int i,j,k;
    mergesort(arr,0,n-1);
    for(i=0;i<n;i++)
        cout<<arr[i];
    return 0;
}
0
ridhim rastogi 20 jul. 2016 a las 17:46

2 respuestas

La mejor respuesta

Solo necesitaba cambiar mid = (low + high) / 2. Gracias @Gerado Gálvez por tu sugerencia

0
ridhim rastogi 21 jul. 2016 a las 03:18

Estás llamando de forma recursiva a mergesort. Aunque su caso general parece legítimo, no puedo determinar su caso base (es decir, salir de la recursividad).

-1
anonymous 20 jul. 2016 a las 21:27