Thread: Mergesort in C

Hello,

For an assignment I have to sort a large amount of numbers with multithreading in C. I am new to C however the part with the threading is going fine. There is some problem with my MergeSort algorithm though, and after staring at it for hours I still can't figure out what the problem is. Maybe someone with a fresh mind..?

Mergesort repeatedly devises an array into two parts, a left and a right part. These parts are sorted recursively and then combined into the resulting array.
(the array is split until the length of one part equals 1, because then left=right and it is trivially sorted)

Code:

void mergesort(int array_to_sort[], int left, int right)
{
    int splitpos;

    if (left < right)
    {
        // Partition the array into two subarrays, sort these subarrays recursively and then merge them into
        // a correctly sorted array.
        splitpos = (left + right) / 2;
        mergesort(array_to_sort, left, splitpos);
        mergesort(array_to_sort, splitpos + 1, right);
        merge(array_to_sort, left, splitpos, right);
        }
}

Now the tricky bit, merging two sorted arrays into the resulting array. Determine sizes of both the first part and the second part of the array. Make auxiliary arrays to temporarely store these parts. Then, walk through both arrays with indices i and j, continuously adding the smallest number of either array. Eventually both arrays have been merged into one.

Code:

void merge(int array_to_sort[], int left, int splitpos, int right)
{
    int size_array1 = splitpos - left + 1;
    int size_array2 = right - splitpos;
    int array1[size_array1];
    int array2[size_array2];
    int i = 0;
    int j = 0;

    // Copy both sub-arrays to auxilary arrays.

    for (i = 0; i < size_array1; i++)
    {
        array1[i] = array_to_sort[left + i];
        }

        for (j = 0; j < size_array2; j++)
        {
        array2[j] = array_to_sort[splitpos + j + 1];
        }

        i = 0;
        j = 0;


        int k;

        for (k = left; k <= right; k ++)
        {
            if ( j = size_array2 )
            { 
            array_to_sort[k] = array1[i];
            i++; 
            }
            else if ( i = size_array1 )
            {
            array_to_sort[k] = array2[j];
            j++; 
            }
            else if (array1[i] <= array2[j])
            {
            array_to_sort[k] = array1[i];
            i++;
            }
            else
            {
            array_to_sort[k] = array2[j];
            j++;
            }
    }
}

The problem is, I get an array with values like -12898313 after sorting an array with integers between 1 and 99. There must be a stupid mistake, but right now, I can't find it. Can you?