Merge sort giving inaccurate results

Question

I was implementing merge sort and I have written some code for it but it is not working as per the given algorithm. Please anyone let me know what's wrong in the code. It is displaying some garbage values as the result. this is the code

Output: Given array is : 85 24 63 45 17 31 96 50 6

Sorted array is: -1 0 0 3 3 31 1 9 85

#include<stdio.h>
#include<stdlib.h>

void merge(int a[],int left, int middle, int right)
{
    int i,j,k;
    int size1=middle-left+1;
    int size2=right-middle;
    int left_array[size1],right_array[size2];

    for(i=0;i<size1;i++)
    left_array[i]=a[left+i];

    for(j=0;j<size2;j++)
    right_array[i]=a[middle+j+1];

    i=0;
    j=0;
    k=left;

    while(i<size1 && j<size2)
    {
        if(left_array[i]<=right_array[j])
        {
            a[k]=left_array[i];
            i++;
        }
        else
        {
            a[k]=right_array[j];
            j++;
        }
        k++;
    }
    while(i<size1)
    {
        a[k]=left_array[i];
        i++;
        k++;
    }
    while(j<size2)
    {
        a[k]=right_array[j];
        j++;
        k++;
    }
}
void merge_sort(int a[],int left, int right)
{
    if(left<right)
    {
        int middle=left+(right-left)/2;
        merge_sort(a,left,middle);
        merge_sort(a,middle+1,right);
        merge(a,left,middle,right);
    }
}
void printArray(int A[], int size)
{
int i;
for (i=0; i <size; i++)
printf("%d ", A[i]);
printf("\n");
}

int main()
{
    int a[] = {85, 24, 63, 45, 17, 31, 96, 50, 6};
    int a_size = sizeof(a)/sizeof(a[0]);

    printf("Given array is: \n");
    printArray(a, a_size);

    merge_sort(a, 0, a_size - 1);

    printf("\nSorted array is: \n");
    printArray(a, a_size);
    return 0;
}

Answer 1

Look carefully here:

void merge(int a[],int left, int middle, int right)
{
    int i,j,k;
    int size1=middle-left+1;
    int size2=right-middle;
    int left_array[size1],right_array[size2];

    for(i=0;i<size1;i++)
    left_array[i]=a[left+i];

    for(j=0;j<size2;j++)
    right_array[i]=a[middle+j+1];
    //          ^                     This should be j.

    // ...
}

Consider using memcpy instead of some raw loops.