Mergesort output changes when printf is used

Question

While trying to craft up a mergesort in C as an exercise, I am encountering a weird issue where the output of the algorithm changes with the presence of a printf. Let me elaborate it further. I have a "MergeSort.h" file in which I have my mergesort algorithm as follows:

#ifndef _MSORT_H_
#define _MSORT_H_

void merge(int a[],int lo,int mi,int hi){
    int n1 = (mi - lo) +1;
    int n2 = hi - mi;
    int left[n1];
    int right[n2];
    int i;
    int j;
    int k;
    for(i = 0;i < n1;i++){
        left[i] = a[lo+i];
    }
    for(j = 0;j < n2;j++){
        right[j] = a[mi+j+1];
    }
    i = 0;
    j = 0;
    for(k = lo;k <= hi;k++){
        if(left[i] < right[j]){
            a[k] = left[i];
            i = i + 1;
        }else{
            a[k] = right[j];
            j = j+1;
        }
    }

}

void msorthelper(int a[],int p,int r){
    if(p < r){
        int mid = (p + r)/2;
        msorthelper(a,0,mid);
        msorthelper(a,mid+1,r);
        merge(a,p,mid,r);
    }
}

void msortex(int a[],int size){
    msorthelper(a,0,size-1);
    int counter;
    for(counter = 0;counter < size;counter++){
        printf(" %d ",a[counter]);
    }
}
#endif

I have my corresponding sort tester in sorttester.c:

#include <stdio.h>
#include "mergesort.h"

int main(){

    int out[] = {8,1,6};
    msortex(out,3);

}

The output from running the sorttester is as follows:

1 0 0

Now here's the interesting part, when I put any printf statement to the beginning of the merge, the correct output is generated. Here's an example:

    #ifndef _MSORT_H_
    #define _MSORT_H_

    void merge(int a[],int lo,int mi,int hi){
        printf("Hello\n"); 
        int n1 = (mi - lo) +1;
        int n2 = hi - mi;
        int left[n1];
        int right[n2];
        .................Rest of the code.....

The output now is:

HelloHello 1 6 8

This is the correct sorted order for the array 8 6 1.

Can somebody tell me what I might be doing wrong here that is causing the output to be drastically by the presence of a printf?

Thanks

Answer 1

Have a look at your merging part of code:

for(k = lo;k <= hi;k++){
    if(left[i] < right[j]){
        a[k] = left[i];
        i = i + 1;
    }else{
        a[k] = right[j];
        j = j+1;
    }
}

Lets assume that

left[] = {1, 2}
right[] = {3, 4, 5}

After 2 iterations of your merging loop (k) the value of "i" will be 2. From now on, you will try to compare

left[2] < right[j]

Which is invalid, as left[2] will refer to some random memory (left array size is only 2, so element of index 2 doesnt exist, only 0 and 1)

So, if you add guards for the i and j values, for example by changing first if condition to:

if(i != n1 && (j == n2 || left[i] < right[j])){

You should be fine.

Anyway, I should also tell you that you shouldnt declare array sizes with values that are not const, like:

int left[n1];
int right[n2];

Its actually forbidden by standard. You should either allocate it dynamically, use vectors(if c++) or jus declare them global with large enough size (maximum n value)