Wrong output in Merge Sort Algorithm

Question

I've followed all the algorithm steps very carefully , but still this always outputs me the wrong answer. I don't understand why. I think something's wrong in the merge algorithm that's causing this but cannot pinpoint what. Please help. Also if there is anything that can be done to improve the code please suggest.

Thank you

INPUT - {5,6,1,8,9,7}

OUTPUT - {1,0,7,0,9,7}

#include<stdio.h>
#include<malloc.h>

void mergeSort(int array[],int length);
void merge(int *leftArray,int *rightArray,int *array);

void main()
{

    int array[] = {5,6,1,8,9,7};
    int length_of_array;

    length_of_array = sizeof(array) / sizeof(array[0]);

    mergeSort(array,length_of_array);

    int i;

    for(i=0;i<length_of_array;i++)
    {
        printf("%d->",array[i]);
    }
}

void mergeSort(int array[],int length)
{

    if(length <  2)
        return;


    int mid;
    int i;

    mid = length/2;

    int *leftArray, *rightArray;

    leftArray = (int*)malloc(mid*sizeof(int));
    rightArray = (int*)malloc((length-mid)*sizeof(int));

    for(i=0;i<mid;i++)
        leftArray[i] = array[i];

    for(i=mid;i<length;i++)
        rightArray[i-mid] = array[i];


    mergeSort(leftArray, mid);
    mergeSort(rightArray, length-mid);

    merge(leftArray,rightArray,array);

}

void merge(int *leftArray,int *rightArray,int *array)
{
    int i,j,k;
    i = j = k = 0;

    int leftSize = sizeof(leftArray)/sizeof(leftArray[0]);
    int rightSize = sizeof(rightArray)/sizeof(rightArray[0]);

    while(i < leftSize && j < rightSize)
    {
        if(leftArray[i]<rightArray[j])
        {
            array[k] = leftArray[i];
            k = k + 1;
            i = i + 1;
        }
        else
        {
            array[k] = rightArray[j];
            k = k + 1;
            j = j + 1;
        }

    }

    while(i<leftSize)
    {
        array[k] = leftArray[i];
        k = k + 1;
        i = i + 1;

    }

    while(j<rightSize)
    {
        array[k]  = rightArray[j];
        k = k + 1;
        j = j + 1;

    }

}

There are zeros in your output, but not in the input. That makes me suspect that you have copied zeros from somewhere esle into your array, probably from beyond the end of the array. — M Oehm, Sep 04 '17 at 11:44
`sizeof(leftArray)` is the same as `sizeof(int*)`. You need to pass the number of elements as parameters. — molbdnilo, Sep 04 '17 at 11:45
Not related to the problem but anyways: [do **not** cast the result of `malloc() in C`.](https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc) — Andre Kampling, Sep 04 '17 at 11:47
Sidenote: Enable all recommended warnings, including `-Wconversion` (gcc, check your compiler for the equivalent). `sizeof` yields a `size_t`, not an `int` and you should not mix unsigned with signed. — too honest for this site, Sep 04 '17 at 11:48
@VineethSai: Get a C book and read the documentation of the tools. The gcc and clang documentation are very clear! — too honest for this site, Sep 04 '17 at 11:54
Also `void main()` is an illegal signature (I wonder why your compiler does not warn, might be another missing warning option). — too honest for this site, Sep 04 '17 at 11:55

lxop · Accepted Answer · 2017-09-04T12:15:21.313

3

As commented by @molbdnilo, you can't get the size of an array from a pointer parameter. So merge needs to take the length of the left and right arrays as well as the pointers to them.

The issue is that arrays in C are not a 'complete' data type, but rather just a convenient syntax. In your merge function, the parameter int *leftArray is exactly what it says - a pointer to an integer. So sizeof will tell you the size of a pointer. In your main function, array is known to be an array, and its length is known (from the initial value given), so sizeof can give the actual size of memory allocated to that variable. But that size is not stored anywhere with the variable, so it is not passed into merge - the only thing passed in is the pointer to the block of memory.

In addition, while it won't be causing you problems in this case, you should be freeing the leftArray and rightArray pointers that you malloc. That way you can use your sorting function in an actual application without leaking memory.

edited Sep 04 '17 at 12:15

answered Sep 04 '17 at 11:59

lxop

7,596
3
27
42

Thank you very much sir , it worked when I passed the value back into the function. Is it possible to tell why exactly it's not possible ? Isn't is the same as sizeof array ? – Vineeth Sai Sep 04 '17 at 12:07
@VineethSai: Because of arrays decaying to pointers, see here: [What is array decaying?](https://stackoverflow.com/questions/1461432/what-is-array-decaying) and [Why sizeof(param_array) is the size of pointer?](https://stackoverflow.com/questions/11622146/why-sizeofparam-array-is-the-size-of-pointer). – Andre Kampling Sep 04 '17 at 12:10
And [Length of array in function argument](https://stackoverflow.com/questions/8269048/length-of-array-in-function-argument) – BLUEPIXY Sep 04 '17 at 12:16
@VineethSai You're welcome. See my edit to the answer – lxop Sep 04 '17 at 12:16

Wrong output in Merge Sort Algorithm

1 Answers1