C语言 归并排序:错误的答案

Question

我正在尝试实现"算法导论"一书中所述的合并排序算法。输出是不正确的，尽管实现在书中指定。很有可能会出现差一的错误，但我不能确定。指针吗?

#include <stdio.h>
#include <stdlib.h>
#define SENTINEL 32767
int* getArray(int size) {
    int* arr;
    int i;
    arr = (int*) malloc(sizeof(int) * size);
    printf("nEnter %d elements:nn", size);
    for (i = 0; i < size; ++i) {
        scanf("%d", (arr + i));
    }
    printf("n");
    return arr;
}
void printArray(int* arr, int size) {
    int i;
    printf("Array[%d]: ", size);
    for (i = 0; i < size; ++i) {
        printf("%d ", arr[i]);
    }
    printf("n");
}
void merge(int* arr, int p, int q, int r) {
    int i, j, k, n1, n2;
    int* left;
    int* right;
    n1 = q - p;
    n2 = r - q;
    left  = (int*) malloc(sizeof(int) * (n1 + 1));
    right = (int*) malloc(sizeof(int) * (n2 + 1));
    left[n1] = right[n2] = SENTINEL;
    for (i = 0; i < n1; ++i) {
        left[i] = arr[p + i];
    }
    for (j = 0; j < n2; ++j) {
        right[j] = arr[q + j];
    }
    i = j = 0;
    for (k = p; k < r; ++k) {
        if (left[i] <= right[j]) {
            arr[k] = left[i++];
        } else {
            arr[k] = right[j++];
        }
    }
}
void mergeSort(int* arr, int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        mergeSort(arr, p, q);
        mergeSort(arr, q + 1, r);
        merge(arr, p, q, r);
    }
}
int main() {
    int* arr;
    int size;
    printf("Enter array size: ");
    scanf("%d", &size);
    arr = getArray(size);
    printArray(arr, size);
    mergeSort(arr, 0, size);
    printArray(arr, size);
    return 0;
}

Answer 1

mergeSort必须以下列方式进行，原因已在评论中说明。

void mergeSort(int* arr, int p, int r) {
    if (r - p > 1) {//for call(a, 0, 1) -> call(a, 0, 1)
        int q = (p + r) / 2;
        mergeSort(arr, p, q);
        mergeSort(arr, q, r);
        merge(arr, p, q, r);
    }
}

还需要free(left);free(right);和free(arr);