Merge sort bug in C

Question

I want to implement merge sort even though it is not required by the class I'm taking.

Below is my code and I have left some printf functions included to demonstrate the bug.

The program seems to work but as I get to my few final merges in the recursion it starts to go outside of the parameters of array and starts comparing garbage values. It works because these values are positive but if one was negative it would store the value inside of my array.

I have attempted to find the bug and the best I can see it has to do with the relational operators but I cannot find the fix.

Any point in the right direction would be greatly appreciated.

#include <stdio.h>

#define SIZE 21

int temp_array[SIZE] = {0};

void sort(int array[], int start, int end);
void merge(int array[], int start_1, int end_1, int start_2, int end_2);

int main()
{

    int array[SIZE] = {10, 1, 8, 3, 6, 5, 4, 7, 2, 9, 0, 100, 91, 98, 93, 96, 95, 94, 97, 92, 99};

    sort(array, 0, SIZE-1);

    for(int i = 0; i < SIZE; i++)
    {
        printf(" %i ", array[i]);
    }

}


void sort(int array[], int start, int end)
{
    if (end > start)
    {
        int middle = (start + end) / 2;

        // sort left half
        printf("sorting left half\n");
        sort(array, start, middle);

        // sort right half
        printf("sorting right half\n");
        sort(array, middle + 1, end);

        // merge the two halves
        printf("####MERGING#####\n");
        merge(array, start, middle, middle + 1, end);

    }
}

void merge(int array[], int start_1, int end_1, int start_2, int end_2)
{
    int counter = 0;
    int s1 = start_1;

    while(start_1<=end_1 && start_2<=end_2)
    {
        printf(" %i %i and %i %i\n", start_1, end_1, start_2, end_2);

        if(array[start_1] < array[start_2])
        {
            printf("selecting %i over %i\n", array[start_1], array[start_2]);
            temp_array[counter++] = array[start_1++];
        }

        else
        {
            temp_array[counter++] = array[start_2++];
            printf("selecting %i over %i\n", array[start_2], array[start_1]);
        }
    }

    while (start_1 <= end_1)
    {
        temp_array[counter++] = array[start_1++];
        printf("Dumping Left Half: placing %i in position %i\n", array[start_1], counter);
    }

    while (start_2 <= end_2)
    {
        temp_array[counter++] = array[start_2++];
        printf(" Dumping Right Half: placing %i in position %i\n", array[start_2], counter);
    }

    for(int i = s1, j = 0; i <= end_2; j++, i++)
    {   
        printf("Placing %i in position %i\n", temp_array[j], i);
        array[i] = temp_array[j];
    }

    return;
}

Answer 1

One thing that looks suspicious to me is this inside that else in your merge code:

temp_array[counter++] = array[start_2++];
printf("selecting %i over %i\n", array[start_2 /* HERE */], array[start_1]);

Assuming start_2 == end_2 holds before the above is executed, then the printf will read from index end_2 + 1, which will be out of bounds in the outermost recursive call of sort and thus undefined behaviour (that might result in printing garbage).