Segfault合并-按C排序

Question

我正在尝试使用合并排序对大小为5500的结构数组进行排序。但是，由于不允许使用VLA，我很快就会遇到分段错误。因此，每次递归调用merge-sort时，我都必须创建2个大小为5500的额外数组。

我很乐意解决我的问题。我将在此处提供我的代码：

void merge(Student rightArr[], Student leftArr[], Student mergedArr[], int sizeOfRight, int sizeOfLeft) {
    int rightArrIndex = 0;
    int leftArrIndex = 0;
    int mergedArrIndex = 0;

    while (leftArrIndex < sizeOfLeft && rightArrIndex < sizeOfRight) {
        char *ptrLeft, *ptrRight;
        long gradeLeft = strtol(leftArr[leftArrIndex].grade, &ptrLeft, BASE_COUNT);
        long gradeRight = strtol(rightArr[rightArrIndex].grade, &ptrRight, BASE_COUNT);
        if (gradeLeft > gradeRight) {
            mergedArr[mergedArrIndex] = rightArr[rightArrIndex];
            rightArrIndex++;
        } else {
            mergedArr[mergedArrIndex] = leftArr[leftArrIndex];
            leftArrIndex++;
        }
        mergedArrIndex++;
    }
    if (leftArrIndex == sizeOfLeft) {
        for (int i = mergedArrIndex; i < (sizeOfLeft + sizeOfRight); i++) {
            mergedArr[i] = rightArr[rightArrIndex];
            rightArr++;
        }
    } else {
        for (int i = mergedArrIndex; i < (sizeOfLeft + sizeOfRight); i++) {
            mergedArr[i] = leftArr[leftArrIndex];
            leftArr++;
        }
    }
}

void mergeSort(Student studentsArray[], int amountOfStudents) {
    if (amountOfStudents <= 1) {
        return;
    }
    int leftSize = (amountOfStudents / 2);
    int rightSize = (amountOfStudents - leftSize);
    Student leftArr[5500], rightArr[5500];
    for (int i = 0; i < leftSize; i++) {
        leftArr[i] = studentsArray[i];
    }
    for (int i = 0; i < rightSize; i++) {
        rightArr[i] = studentsArray[i + leftSize];
    }
    mergeSort(leftArr, leftSize);
    mergeSort(rightArr, rightSize);
    merge(rightArr, leftArr, studentsArray, rightSize, leftSize);
}

Answer 1

好吧，我认为这应该做您想要的。假定已定义Student和BASE_COUNT：

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

void merge(Student studentsArr[],
           int leftSize, int rightSize,
           Student scratchArr[])
{
    Student *leftArr = studentsArr;
    Student *rightArr = studentsArr + leftSize;
    int leftIx = 0, rightIx = 0, mergeIx = 0, ix;

    while (leftIx < leftSize && rightIx < rightSize) {
        long gradeLeft = strtol(leftArr[leftIx].grade, NULL, BASE_COUNT);
        long gradeRight = strtol(rightArr[rightIx].grade, NULL, BASE_COUNT);

        if (gradeLeft < gradeRight) {
            scratchArr[mergeIx++] = leftArr[leftIx++];
        }
        else {
            scratchArr[mergeIx++] = rightArr[rightIx++];
        }
    }

    while (leftIx < leftSize) {
        scratchArr[mergeIx++] = leftArr[leftIx++];
    }

    // Copy the merged values from scratchArr back to studentsArr.
    // The remaining values from rightArr (if any) are already in
    // their proper place at the end of studentsArr, so we stop
    // copying when we reach that point.

    for (ix = 0; ix < mergeIx; ix++) {
        studentsArr[ix] = scratchArr[ix];
    }

}

void mergeSortInternal(Student studentsArray[],
                       int amountOfStudents,
                       Student scratchArr[])
{
    if (amountOfStudents <= 1) {
        return;
    }

    int leftSize = amountOfStudents / 2;
    int rightSize = amountOfStudents - leftSize;

    mergeSortInternal(studentsArray, leftSize, scratchArr);
    mergeSortInternal(studentsArray + leftSize, rightSize, scratchArr);

    merge(studentsArray, leftSize, rightSize, scratchArr);
}

#define MAX_ARR_SIZE    5500

void mergeSort(Student studentsArray[], int amountOfStudents)
{
    if (amountOfStudents <= 1) {
        return;
    }

    if (amountOfStudents > MAX_ARR_SIZE) {
        fprintf(stderr, "Array too large to sort.\n");
        return;
    }

    Student scratchArr[MAX_ARR_SIZE];

    mergeSortInternal(studentsArray, amountOfStudents, scratchArr);
}

顶级排序功能为mergeSort，在原始帖子中定义。它声明了一个大小为MAX_ARR_SIZE的单个暂存数组，定义为5500。顶层函数本身不是递归的，因此此暂存数组仅分配一次。