CODEWITHSUNDEEP
calgorithmmergesort
Vineeth Sai
Vineeth Sai

Reputation: 3447

Wrong output in Merge Sort Algorithm

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;

    }

}

Upvotes: 0

Views: 88

Answers (1)

lxop
lxop

Reputation: 8595

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.

Upvotes: 3

Related Questions