C# Merge Sort creates stack overflow error

Question

I know there's a decent amount of posts on this exact topic, but I can't seem to use any of them to fix what I have. I'm assuming that my first line

if (array.Length > 1)

is somehow creating the error but I'm not sure how. This is the code.

public static string[] MergeSort(string[]array)
    {
        if (array.Length > 1)
        {
            int mid = array.Length / 2;
            string[] lefthalf = new string[mid];
            for (int l = 0; l < mid; l++)
            {
                lefthalf[l] = array[l];
            }
            string[] righthalf = new string[mid + 1];
            for (int r = mid; r < righthalf.Length ; r++)
            {
                righthalf[r] = array[r];
            }
            MergeSort(lefthalf);
            MergeSort(righthalf);
            int i = 0;
            int j = 0;
            int k = 0;
            while (i < lefthalf.Length && j < righthalf.Length)
            {
                if (String.Compare(lefthalf[i],righthalf[j]) == -1)
                {
                    array[k] = lefthalf[i];
                    i += 1;
                }
                else
                {
                    array[k] = righthalf[k];
                    j += 1;
                }
                k = k + 1;
            }

            while (i< lefthalf.Length)
            {
                array[k] = lefthalf[i];
                i += 1;
                k += 1;
            }
            while (j < righthalf.Length)
            {
                array[k] = righthalf[j];
                j += 1;
                k += 1;
            }
        }
        return array;
    }

array starts of as an array of 100 strings. When I attempt to use this procedure, the program returns this error:

System.StackOverflowException: 'Exception of type 'System.StackOverflowException' was thrown.'

After being told to in the comments, I've attempted to debug, it seems to be in an infinite loop of creating an array of length 2 with null as the first element, and the second element the second string in my first array. It never seems to pull it out and bring it to the next stage of the merge sort.

Any help would be appreciated.

Answer 1

For recursion you need to put a return in front of the recursive calls to MergeSort, otherwise the recursive loop will never exit and you just keep stacking calls, to the MergeSort function, on the call stack. Also the second call to MergeSort will never actually get called, the first recursive call exits the function before it can execute.

You're basically looping from the start of the function to the first recursive call to that function.