Почему мой базовый вариант (ошибочно) запускается немедленно?

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

Ваш базовый случай запускается, потому что так работают рекурсивные алгоритмы. Ты продолжаешь звонитьsplit()снова и снова с нижним и нижним промежутком между lowerBound и upperBound, так что в конечном итоге срабатывает ваш базовый случай. И это должно быть хорошо, поскольку запуск базового случая позволяет вам знать, что ваши входные "массивы" (синглтоны) отсортированы и могут быть объединены.

Причина, по которой он запускается "немедленно", заключается в том, что он должен: split() вызывается постоянно, пока не будет выполнен базовый вариант, поэтому первый оператор печати, который вы увидите, является оператором базового случая.