我是C 语言的新手（我在做CS50x），想实现一个归并排序算法。我想调试我的代码，但我还没弄清楚为什么 malloc 在 sort_disassemble 中会崩溃。

附言：代码还没写完，这只是测试用。

#include <time.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define LEN 8
int validcount = 0;
int *singlep[LEN];

typedef struct 
{
    int *first;
    int *second;
} SplitP;

void sort(int *arr, int ln);
SplitP sort_desassemble(int *arr, int len);
int sort_reassemble(int *right, int *left, int lenright, int lenleft);

int main(void)
{
    int *arr = malloc(sizeof(int) * LEN);

    // Randomly generate the array
    srand(time(NULL)); // Seed ONCE before the loop

    for (int i = 0; i < LEN; i++)
    {
        int n = rand() % 11;  // Generates 0 to 10
        *(arr + i) = n;
    }

    // Print the unsorted
    printf("unsorted: ");
    // Print the sorted list
    for (int i = 0; i < LEN; i++)
    {
        printf("%i,", *(arr + i));
    }
    printf("\n");

    // Sort it
    sort(arr, LEN);

    printf("sorted: ");
    // Print the sorted list
    for (int i = 0; i < LEN; i++)
    {
        printf("%i", *(singlep + i));
    }
    printf("\n");
}

void sort(int *arr, int ln)
{
    // Base
    if (ln == 1)
    {
        // Store it in the pointer array of values
        *(singlep + validcount) = arr;
        validcount++;
        return;
    }

    // get the two parts
    SplitP val = sort_desassemble(arr, ln);
    int firstln = 0, secondln = 0;

    // First will always be the same
    firstln = ln / 2;

    if (ln % 2 == 0)
    {
       secondln = ln / 2;
    }
    else // ln is odd 
    {
        secondln = ln % 2 + firstln;
    }

    sort(val.first, firstln);
    sort(val.second, secondln);
}

// This function will return an array of pointers that point to the desassembled arrays
SplitP sort_desassemble(int *arr, int len)
{
    const int HALF = len / 2;
    int *newarr = malloc(HALF * sizeof(int));
    SplitP value;

    // First part
    for (int i = 0; i < HALF; i++)
    {
        *(newarr + i) = *(arr + i);
    }

    int *newarr2 = malloc(HALF * sizeof(int));
    // Second part
    for (int i = HALF; i < len; i++)
    {
        *(newarr2 + i) = *(arr + i);
    }

    value.first = newarr;
    value.second = newarr2;

    return value;
}

// right and left should point to the start of two arrays
int sort_reassemble(int *right, int *left, int lenright, int lenleft)
{
    // I can use arrays but i want practice on malloc
    int *arr = malloc((lenright + lenleft) * sizeof(int));
    int leftindex = 0, rightindex = 0;

    // I was confusion i and j so i gave them appropriate names.
    while ((leftindex < lenleft) && (rightindex < lenright))
    {
        if (*(left + leftindex) < *(right + rightindex))
        {
            // i and j design the index of the area we want to put our number
            *(arr + (leftindex + rightindex)) = *left;
            leftindex++;
        }

        else if (*(right + rightindex) < *(left + leftindex))
        {
            *(arr + (leftindex + rightindex)) = *right;
            rightindex++;
        }

        else // If there are equal
        {
            *(arr + (leftindex + rightindex)) = *(right + rightindex);
            *(arr + (leftindex + rightindex + 1)) = *(left + leftindex);
            rightindex++;
            leftindex++;
        }
    }

    return *arr;
}

解决方案

*(newarr2 + i) 应该是 *(newarr2 + (i - HALF))。此外，newarr2 应该是 malloc((HALF + (len % 2)) * sizeof(int)) 或 malloc((len - HALF) * sizeof(int))，而不是 malloc(HALF * sizeof(int))，否则当 len 为奇数时，*(newarr2 + (i - HALF)) 将导致下标越界（未定义行为，可能会崩溃）。

修复后的完整代码：

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct {
    int* first;
    int* second;
} SplitP;

void sort(int* arr, int ln);
SplitP sort_desassemble(int* arr, int len);
int* sort_reassemble(int* right, int* left, int lenright, int lenleft);

int main() {
    const int LEN = 8;
    int* arr = malloc(sizeof(int) * LEN);

    // Randomly generate the array
    srand(time(NULL));  // Seed ONCE before the loop

    for (int i = 0; i < LEN; i++) {
        int n = rand() % 11;  // Generates 0 to 10
        *(arr + i) = n;
    }

    // Print the unsorted
    printf("unsorted: ");
    for (int i = 0; i < LEN; i++) {
        printf("%i ", *(arr + i));
    }
    printf("\n");

    // Sort it
    sort(arr, LEN);

    printf("sorted: ");
    // Print the sorted list
    for (int i = 0; i < LEN; i++) {
        printf("%i ", *(arr + i));
    }
    printf("\n");

    // Free the initial array memory
    free(arr);
    return 0;
}

void sort(int* arr, int ln) {
    // Base case: if length is 1 or less, it's already sorted
    if (ln <= 1) {
        return;
    }

    // Split the array into two parts
    SplitP val = sort_desassemble(arr, ln);
    int firstln = ln / 2;
    int secondln = ln - firstln;

    // Recursively sort both halves
    sort(val.first, firstln);
    sort(val.second, secondln);

    // Merge the sorted halves back together
    int* merged = sort_reassemble(val.second, val.first, secondln, firstln);

    // Copy the merged values back into the original array
    for (int i = 0; i < ln; i++) {
        *(arr + i) = *(merged + i);
    }

    // Free temporary memory to prevent leaks
    free(val.first);
    free(val.second);
    free(merged);
}

// Returns a struct containing pointers to two new allocated subarrays
SplitP sort_desassemble(int* arr, int len) {
    const int HALF = len / 2;
    int* newarr = malloc(HALF * sizeof(int));
    SplitP value;

    // Copy first part
    for (int i = 0; i < HALF; i++) {
        *(newarr + i) = *(arr + i);
    }

    int secondSize = len - HALF;
    int* newarr2 = malloc(secondSize * sizeof(int));

    // Copy second part
    for (int i = HALF; i < len; i++) {
        *(newarr2 + (i - HALF)) = *(arr + i);
    }

    value.first = newarr;
    value.second = newarr2;

    return value;
}

// Merges two sorted arrays into a single new sorted array
int* sort_reassemble(int* right, int* left, int lenright, int lenleft) {
    int* arr = malloc((lenright + lenleft) * sizeof(int));
    int leftindex = 0, rightindex = 0;
    int k = 0;  // index for the merged array

    // Compare elements from both arrays and pick the smaller one
    while ((leftindex < lenleft) && (rightindex < lenright)) {
        if (*(left + leftindex) <= *(right + rightindex)) {
            *(arr + k) = *(left + leftindex);
            leftindex++;
        } else {
            *(arr + k) = *(right + rightindex);
            rightindex++;
        }
        k++;
    }

    // Append remaining elements from left array if any
    while (leftindex < lenleft) {
        *(arr + k) = *(left + leftindex);
        leftindex++;
        k++;
    }

    // Append remaining elements from right array if any
    while (rightindex < lenright) {
        *(arr + k) = *(right + rightindex);
        rightindex++;
        k++;
    }

    return arr;
}

编辑：将 (int*)malloc 替换为 malloc，因为据chux的建议，这种强制转换只在C++中才需要。