0

I'm trying to code MergeSort algorithm myself but I got to the point, when I'm not sure what is wrong so the algorithm is not working. I basically do everything like goes in mergesort algorithm, finding mid, splitting and merging. Code goes here:

void merge(int *aux1, int *aux2, int *array) {
    int p1 = 0, p2 = 0, i;
    //debug
    printf("MERGE! sizeof aux1:%d, aux2:%d", SIZEOF_ARRAY(aux1), SIZEOF_ARRAY(aux2));
    printf(" MERGE!sizeof array:%d\n", SIZEOF_ARRAY(array));

    for (i = 0; i < SIZEOF_ARRAY(array); i++) {
        if ((aux1[p1] > aux2[p2]) && (p2 != SIZEOF_ARRAY(aux2))) {
            array[i] = aux2[p2];
            p2++;
        } else {
            array[i] = aux1[p1];
            p1++;
       }
   }

}

void mergeSort(int *array, int l, int r) {
    if (l < r) {
        int m = (l + r) / 2; //finding mid of array

        int aux1[m - l + 1], aux2[r - m]; //create temporary arrays
        int i;
        //debug
        printf("MERGESORT sizeof aux1:%d, aux2:%d\n", SIZEOF_ARRAY(aux1), SIZEOF_ARRAY(aux2));

        //split arrays
        for (i = l; i <= m; i++)
            aux1[i - l] = array[i];

        for (i = m + 1; i <= r; i++)
            aux2[i - (m + 1)] = array[i];

        mergeSort(aux1, l, m);
        mergeSort(aux2, m + 1, r);

        merge(aux1, aux2, array);
    }
}

The issue with the code is that when I try to debug it and I get to the point when mergeSort stops and it comes to merge the very first 2 elements of the array, in merge function, the macro SIZEOF_ARRAY(aux1) or SIZEOF_ARRAY(aux2) shows, that they (aux1[] and aux2[]) are 2 elements long, while in mergeSort function the same macro shows they have only 1 element which is correct. I totally don't know what is happening because I'm using the same temporary arrays, but macro shows different lengths. Macro code is:

#define SIZEOF_ARRAY(a) (sizeof( a ) / sizeof( a[ 0 ] ))

Any help would be appreciated. THANKS!!!

chqrlie
  • 131,814
  • 10
  • 121
  • 189
qwerty_
  • 137
  • 1
  • 1
  • 8
  • better parenthesize `a` in the macro: `#define SIZEOF_ARRAY(a) (sizeof(a) / sizeof((a)[0]))` – chqrlie Jan 18 '16 at 01:00
  • You need to pass the array sizes as extra arguments to your `merge` function, they cannot be determined from the pointers alone. – chqrlie Jan 18 '16 at 01:04
  • @chqrlie this is actually what i did and it solved my issue :) – qwerty_ Jan 18 '16 at 01:09
  • note that your merge code is incorrect: you must test subarray boundaries before attempting to access their elements. The test should read: `if (p1 >= size1 || aux1[p1] > aux2[p2])`. A single test is sufficient because `p1` and `p2` cannot both be at the end of their subarrays. – chqrlie Jan 18 '16 at 01:14

0 Answers0