[FIXED] What in the source is causing platform dependent results

Issue

I wrote the merge sort algorithm in C and have compiled it both locally and remotely. I assume something in the source is causing platform dependence.

#include <stdio.h>
#include <limits.h>
#include <math.h>

void merge(int A[], int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q;

    int L[n1];
    int R[n2];

    for (int i = 0; i < n1; ++i) {
        L[i] = A[p + i];
    }

    for(int j = 0; j < n2; ++j) {
        R[j] = A[q + j + 1];
    }

    L[n1] = INT_MAX;
    R[n2] = INT_MAX;

    int i = 0;
    int j = 0;

    for (int k = p; k <= r; ++k) {
        if (L[i] <= R[j]) {
            A[k] = L[i];
            i = i + 1;
        } else {
            A[k] = R[j];
            j = j + 1;
        }
    }
}

void merge_recurse(int A[], int p, int r) {
    if (p < r) {
        int q = floor((p + r) / 2);
        merge_recurse(A, p, q);
        merge_recurse(A, q + 1, r);
        merge(A, p, q, r);
    }
}

void merge_sort(int A[], size_t length) {
    merge_recurse(A, 0, (int)length - 1);
}

int main() {
    int length = 9;
    int A[] = { 3, 7, 61, 3, 40, 4, -1, 8, 10 };

    merge_sort(A, length);

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

    return 0;
}

When compiled online the correct result is returned.

-1, 3, 3, 4, 7, 8, 10, 40, 61,

However when I compile the source locally on Linux an incorrect result is returned.

-1, 4, 8, 10, 2147483647, 3, 7, 40, 61

What in the source code causes these different results?

Solution

L[n1] = INT_MAX; writes past the end of the array. The declaration int L[n1]; creates an array that can be indexed from 0 to n1-1. There is no L[n1]. Same thing for R[n2] = INT_MAX;

When code writes past the end of an array, it may stomp on another variable in a way that changes the behavior of the code. Or it might not have any observable effect. The online compiler just happened to arrange the variables in memory in a way that nothing bad happened. It's completely unpredictable, and known as undefined behavior.

Answered By - user3386109

Answer Checked By - Clifford M. (PHPFixing Volunteer)