为什么我的基本情况被（错误）立即触发？

Question

我正在尝试在C中实现合并排序算法。在递归数组拆分功能中，尽管有return语句，我的基本情况仍会无限发生，并且永远不会调用合并功能。这是我的代码：

#include <stdio.h>

const int MAX = 1000;

int getArray(int unsorted[MAX], int upperBound)
{
    int i;
    for(i = 0; i <= upperBound; ++i)
    {
        printf("Now enter integer number %d: ", i + 1);
        scanf("%d", &unsorted[i]);
        while((getchar()) != '\n');
    }   
    printf("\n");
    return 0;
}

int merge(int unsorted[MAX], int sorted[1000], int lowerLeft, int lowerRight)
{
    if(lowerLeft == lowerRight)
        return 0;
    int j = lowerRight;
    for(int i = lowerLeft; i < lowerRight; ++i)
    {
        if(unsorted[i] <= unsorted[j])
        {
            sorted[i] = unsorted[i];
            ++j;
        }
        else
        {
            sorted[i] = unsorted[j];
            ++j;
        }
    }
    return 1;
}

int split(int unsorted[MAX], int sorted[1000], int lowerBound, int upperBound)
{
    printf("%d is the lBound and %d is the uBound\n", lowerBound, upperBound);
    if(lowerBound == upperBound)
    {
        printf("\nBase case triggered.");
        getchar();
        return 0;
    }
    int middle = upperBound/2;
    split(unsorted, sorted, 0, middle);
    split(unsorted, sorted, middle + 1, upperBound);    
    merge(unsorted, sorted, lowerBound, middle);
    return 1;
}

int main()
{
    int unsorted[MAX];
    int sorted[MAX];
    int lowerBound = 0;
    int upperBound;

    printf("First enter the number of integers you wish to sort: ");
    scanf("%d", &upperBound);
    while((getchar()) != '\n');
    printf("\n");
    upperBound = upperBound - 1;
    getArray(unsorted, upperBound);
    split(unsorted, sorted, lowerBound, upperBound);
    printf("\n");
    for(int c = 0; c < upperBound; ++c)
    {
        printf("%d, ", sorted[c]);
    }

    return 0;
}

为什么在达到基本情况后不调用合并功能？抱歉，如果我不能方便地回答问题，希望有人可以在这里帮助我，谢谢。

Answer 1

您的基本情况已被触发，因为这就是递归算法的工作方式。您不断在LowerBound和upperBound之间的间隙越来越小，一遍又一遍地调用split()，因此最终触发了基本情况。那应该是一件好事，因为触发基本情况会让您知道您的输入“数组”（单子）已排序并且可以合并。

“立即”被触发的原因是它必须：split（）被连续调用，直到满足基本情况为止，所以您将看到的第一个print语句是基本情况。