Ошибка в функции слияния (сортировка слияния)

Question

Я пытаюсь реализовать алгоритм сортировки слиянием, как указано в книге алгоритмов CLRS. Я придумал следующий код.

#include<stdio.h> 
#include<stdlib.h> 
void merge_sort(int *arr,int start_index,int end_index); 
void merge(int *arr,int start_index,int middle_index,int end_index); 

int main(){ 

int arr[]={5,2,1,6,0,3,3,4}; //8 elements last index 7 
int i; 
printf("Before sorting.\n"); 
for(i=0;i<8;i++) 
printf("%d,",arr[i]); 
merge_sort(arr,0,7); 
printf("\nAfter sorting.\n"); 
for(i=0;i<8;i++) 
printf("%d,",arr[i]); 

return 0;} 

void merge_sort(int *arr,int start_index,int end_index){ 
    int middle_index; 
    if(start_index<end_index) 
    { 
     middle_index=(start_index+end_index)/2; 
     merge_sort(arr,start_index,middle_index); 
     merge_sort(arr,(middle_index+1),end_index); 
     merge(arr,start_index,middle_index,end_index); 
    } 

} 

void merge(int *arr, int start_index,int middle_index, int end_index){ 

    int n1,n2,i,l,m; 
    n1=middle_index-start_index+1; 
    n2=end_index-middle_index; 
    int sub_arr1[n1+1],sub_arr2[n2+1]; 
    for(i=0;i<=(n1-1);i++) 
     sub_arr1[i]=arr[i]; 
    for(i=0;i<=(n2-1);i++) 
     sub_arr2[i]=arr[middle_index+1+i]; 

    sub_arr1[n1]=100; 
    sub_arr2[n2]=100; 
     l=0,m=0; 
    for(i=0;i<=end_index;i++){ 


     if(sub_arr1[l]<sub_arr2[m]) 
     {arr[i]=sub_arr1[l]; 
     l=l+1;} 
     else 
     {arr[i]=sub_arr2[m]; 
     m=m+1;} 

    }} 
There seems to be some error in the merge function due to which I am getting an erroneous output which is as follows. 

Before sorting. 
5,2,1,6,0,3,3,4, 
After sorting. 
2,4,100,-1076668400,2,4,100,7, 
RUN FINISHED; exit value 0; real time: 0ms; user: 0ms; system: 0ms 

Поскольку числа, которые я сортирую с помощью этого метода, являются небольшими, я использовал 100 в качестве контрольной суммы. Может ли это быть источником ошибок? Любая помощь оценивается.

Answer 1

У вас есть ошибка в вашей функции слияния: вы игнорируете start_index. Эти строки:

for(i=0;i<=(n1-1);i++) 
    sub_arr1[i]=arr[i]; 

должны быть заменены:

for(i=0;i<=(n1-1);i++) 
    sub_arr1[i]=arr[start_index+i]; 

И последний цикл, должен, вместо этого, начать с I = start_index:

for (i=start_index;i<=end_index;i++) { /* ... */ } 

я улучшил отступа немного немного. Ниже приведена окончательная рабочая версия слияния():

void merge(int *arr, int start_index,int middle_index, int end_index) { 
    int n1,n2,i,l,m; 
    n1=middle_index-start_index+1; 
    n2=end_index-middle_index; 
    int sub_arr1[n1+1],sub_arr2[n2+1]; 
    for (i=0;i<=(n1-1);i++) 
     sub_arr1[i]=arr[start_index+i]; 
    for (i=0;i<=(n2-1);i++) 
     sub_arr2[i]=arr[middle_index+1+i]; 
    sub_arr1[n1]=100; 
    sub_arr2[n2]=100; 
    l=0,m=0; 
    for (i=start_index;i<=end_index;i++) { 
     if(sub_arr1[l]<sub_arr2[m]) { 
      arr[i]=sub_arr1[l]; 
      l=l+1; 
     } 
     else { 
      arr[i]=sub_arr2[m]; 
      m=m+1; 
     } 
    } 
} 

Протестировано и работает.