Почему этот алгоритм слияния не работает?

Question

Я пробовал следующий код в C для mergesort, но он просто заканчивается тем, что дает мне segfault. Может ли кто-нибудь найти ошибку?

int mergesort(int* unsorted, int* sorted, int N) { 
if (N==1) { 
    *unsorted=*sorted; 
    return 1; 
} 
else { 
    int left[MAXLEN]; 
    int right[MAXLEN]; 
    int sleft[MAXLEN]; 
    int sright[MAXLEN]; 
    int k1 = fill(unsorted,left,0,N/2); 
    int k2 = fill(unsorted,right,N/2,N); 
    int l1 = mergesort(left,sleft,k1); 
    int l2 = mergesort(right,sright,k2); 
    merge(sorted,sleft,sright,l1,l2); 
    return N; 
} 
} 

void merge(int* sorted,int* left,int* right,int N1,int N2) { 
int i1=N1; 
int i2=N2; 
while ((i1!=0) || (i2!=0)) { 
    if (i1==0) { 
     while ((i2--)!=0) 
      *sorted++=*right++; 
    } 
    else if (i2==0) { 
     while ((i1--)!=0) 
      *sorted++=*left++; 
    } 
    else { 
     if (*left < * right) { 
      *sorted++=*left++; 
      i1--; 
     } 
     else { 
      *sorted++=*right++; 
      i2--; 
     } 
    } 
} 
} 

Функция заполнения реализована следующим образом

int fill(int* from, int* to, int left, int right) { 
int i = left; 
from += i; 
while (i<right) { 
    *to++=*from++; 
    i++; 
} 
return (right-left); 

}

Может кто-нибудь объяснить, является ли это ошибка, или я не обрабатывается должным образом выделение памяти?

Answer 1

• Изменить условия слияния функция

while ((i1!=0) || (i2!=0))

() в

while ((i1>0) || (i2>0))

Это удалит Segfault.

Объяснение: Пусть i1=0 и i2=1. Тогда посмотрим, что произойдет:

if (i1==0) { 
     while ((i2--)!=0) 
      *sorted++=*right++; 
    } 

Когда проверка компилятор i2 это 1. Поэтому условие true. Петля продолжается, и она уменьшает i2 на 1. Итак, теперь i2=0
на следующей итерации, когда компилятор снова проверит i2, который равен 0. Условие false. Loop breaks и, как вы видите, i2 декретов 1. Таким образом, i2 становится i2=-1. Потому что при первых проверках компилятора i2 затем уменьшается.

Таким образом, это while ((i1!=0) || (i2!=0)) условие никогда не выполняется, и * отсортированный ++ постоянно увеличивается и вызывает segmfault по мере того, как вы исчерпали пространство стека.

• Теперь измените первое условие функции mergesort().

То есть:

if (N==1) { 
    *unsorted=*sorted; 
    return 1; 
} 

в

if (N==1) { 
    *sorted=*unsorted; 
    return 1; 
} 

Объяснение: Если вы делаете 1-ый, отсортированный массив никогда не изменится, и вы никогда не будет отсортирован. Поэтому, когда осталось только один элемент, мы можем просто скопировать элемент несортированного массива в отсортированный.

Я думаю, что это решит проблему :)