C＃Merge Sort创建堆栈溢出错误

Question

我知道在这个确切的主题上有相当数量的帖子，但我似乎无法使用其中任何一个来修复我的内容。我假设我的第一行

if (array.Length > 1)

以某种方式创建错误，但我不知道如何。这是代码。

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;
    }

数组以100个字符串的数组开头。当我尝试使用此过程时，程序返回此错误：

System.StackOverflowException：'抛出类型'System.StackOverflowException'的异常。

在评论中被告知后，我试图调试，它似乎是在一个无限循环中创建一个长度为2的数组，其中null为第一个元素，第二个元素是第一个数组中的第二个字符串。它似乎永远不会把它拉出来并将它带到合并排序的下一个阶段。

任何帮助，将不胜感激。

Answer 1

对于递归，您需要在对MergeSort的递归调用之前放置一个返回，否则递归循环将永远不会退出，您只需在调用堆栈上保持对MergeSort函数的堆栈调用。第二次调用MergeSort永远不会被调用，第一次递归调用会在函数执行之前退出。

您基本上是从函数的开头循环到对该函数的第一次递归调用。