0

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;

    }

}
11
  • 3
    1. Use a debugger. 2. Thisfor(i=mid;i<length;i++)mightbeperfectly"readable"forthecompilerbutnotsoforhumans. Commented Sep 4, 2017 at 11:44
  • 2
    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. Commented Sep 4, 2017 at 11:44
  • 5
    sizeof(leftArray) is the same as sizeof(int*). You need to pass the number of elements as parameters. Commented Sep 4, 2017 at 11:45
  • 1
    Not related to the problem but anyways: do not cast the result of malloc() in C. Commented Sep 4, 2017 at 11:47
  • 1
    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. Commented Sep 4, 2017 at 11:48

1 Answer 1

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.

Sign up to request clarification or add additional context in comments.

4 Comments

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 ?
@VineethSai: Because of arrays decaying to pointers, see here: What is array decaying? and Why sizeof(param_array) is the size of pointer?.
@VineethSai You're welcome. See my edit to the answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.