Why is my base case being (erroneously) triggered immediately?

Question

I am trying to implement a merge sort algorithm in C. In the recursive array split function, my base case is occurring infinitely, despite the return statement, and the merge function is never called. Here is my code:

#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;
}

Why won't the merge function be called after reaching the base case? Sorry if I didn't phrase the question conveniently, hoping someone can help me out here, thanks.

Answer 1

Your base case is being triggered because that's how recursive algorithms work. You keep calling split() over and over again with a lower and lower gap between lowerBound and upperBound, so eventually your base case gets triggered. And that should be a good thing, since triggering the base case lets you know that your input "arrays" (singletons) are sorted and can be merged.

The reason it gets triggered "immediately" is that it must: split() gets called continually until the base case is met, so the first print statement you'll see is the base case one.