Mergesort sorting algorithm error

Question

I am having a problem with an mergesort sort algorithm in which the output of the ordered vector appears a repeated number and also a memory address. Follow the code:

Mergesort

/*Funcao que implementa o mergeSort*/
void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;

    /* cria um array temporario*/
    int L[n1], R[n2];

    /* Copia os dados para os arrays temporarios L[] e R[] */
    for (i = 0; i < n1; i++) {
        L[i] = arr[l + i];
    }
    for (j = 0; j < n2; j++) {
        R[j] = arr[m + 1 + j];
    }

    /* Merge os arrays temporarios de volta para o array[l..r]*/
    i = 0; /*index inicial do primeiro subarray*/
    j = 0; /*index inicial do segundo subarray*/
    k = l; /*index inicial do array merged*/
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /*Copia os elementos restantes para L[], se houver algum*/
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    /*Copia os elementos restantes para R[], se houver algum*/
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}


/*L e para o index da esquerda e r para o index da direita do
subarray de A que vai ser sorted*/
void mergeSort(int arr[], int l, int r)
{
    if (l < r) {
        /* O mesmo que (l+r)/2, mas evita overflow de l grande e h*/
        int m = l+(r-l)/2;

        /*Sort primeira e segunda metade */
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);
    }
}

Print (Function that prints the vector)

void print(int *A, int n) {
    printf("[");
    for(int i = 0; i < n; i++) {
        printf(" %i ", A[i]);
    }
    printf("]");
    printf("\n\n");
}

Main

int main(int argc, char const *argv[]) {
    int A[] = {1,7,3,8,5,2,9};
    int n = sizeof(A)/4;

    print(A,n);

    stoogeSort(A,0,n);

    print(A,n);

    return 0;
}

Exit

vetor desordenado
[ 1  7  3  8  5  2  9 ]

vetor ordenado
[ 1  2  3  5  7  7  8  9  6422300 ]

What could be the problem? I realized that after passing the "n" as parameter of the mergeSort function, its value is changed, but I do not know how it happens.

Answer 1

Whenever you see random values should distrust:

ordered vector
[ 1 2 3 5 7 7 8 9 6422300 ]
                             ^^^^^^

Most of the time it means that you’re accessing parts of the memory that you shouldn’t and so it represents undefined behavior. In his example is precisely what is happening!

Your call to the Sort:

stoogeSort(A,0,n);

It was done by passing n when it should be passed with n - 1, and so it should be so:

stoogeSort(A,0,n - 1);

How did you get by n, the function accessed more values in memory than it should and ended up overriding values of variables, in the case it hit its variable n which was modified at the end of the ordination.

See the code working with this change

Note: Do not assume the size of a int is always 4 bytes, as it did in int n = sizeof(A)/4;. Do the right thing and refer to the size of int with sizeof(int).

Answer 2

For some reason, the value you are passing from N is changing. Therefore, I suggest you use a #define N 6 instead of int n = sizeof(A)/4.