Вычисление m для среднего элемента является поддельным: вы получаете смещение m от s, а не его индекс в массиве.
Вот исправленная версия:
void mergeSort(int s, int e, int n[]) {
if (s < e) {
int m = s + (e - s + 1) / 2;
mergeSort(s, m - 1, n);
mergeSort(m, e, n);
merge(s, e, m, n);
}
}
В вашем коде есть другие проблемы, а именно:
- Вы должны проверить смещения
i и j до dereferencing a1 [i] and a2 [j] `.
- смещение
k не должно использоваться непосредственно в фазе слияния, его следует хранить в n[s + k].
- в цикле инициализации для
a2, вы должны использовать a2[j] = n[m + j]; вместо a2[j] = n[s + m + j];
Обратите внимание, что идиоматично передавать диапазоны в C с включенным первым индексом и последним исключенным индексом. Это позволяет пропускать пустые диапазоны, чего нет у вашего текущего метода. Это также делает код намного проще и легче для чтения.
Вот модифицированная версия:
#include <stdio.h>
void merge(int s, int e, int m, int n[]) {
int l1 = m - s;
int l2 = e - m;
int a1[l1];
int a2[l2];
for (int i = 0; i < l1; i++) {
a1[i] = n[s + i];
}
for (int j = 0; j < l2; j++) {
a2[j] = n[m + j];
}
for (int i = 0, j = 0, k = 0; k < l1 + l2; k++) {
if (i < l1 && (j >= l2 || a1[i] <= a2[j])) {
n[s + k] = a1[i];
i++;
} else {
n[s + k] = a2[j];
j++;
}
}
}
void mergeSort(int s, int e, int n[]) {
if (e > s + 1) {
int m = s + (e - s) / 2;
mergeSort(s, m, n);
mergeSort(m, e, n);
merge(s, e, m, n);
}
}
int main(void) {
int n[] = { 4, 3, 2, 1 };
int r = sizeof(n) / sizeof(n[0]);
mergeSort(0, r, n);
for(int i = 0; i < r; i++) {
printf("%i\n", n[i]);
}
return 0;
}