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

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

#include #include 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 в качестве контрольного значения. Может ли это быть источником ошибок? Любая помощь оценивается.

У вас есть ошибка в вашей функции слияния: вы игнорируете 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]; 

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

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

Я немного улучшил отступы. Вот окончательная рабочая версия merge ():

 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] 

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