c# - C# 中的简单归并排序

Question

我一直在对排序算法进行小修改，并遇到了合并排序。我已经编写了代码，并在最后一个小时内对其进行了修改，以确定它为何无法正常工作。我收到标准 StackOverFlow 异常。谁能告诉我算法有什么问题吗？提前致谢。这是我到目前为止所写的内容:

public Int32[] MergeSort(Int32[] array)
{
    int counter = 0;
    if (array.Length == 0) { return array; }
    int mid = array.Length / 2;
    Int32[] leftHalf = new Int32[mid+1];
    Int32[] rightHalf = new Int32[mid+1];
    for (int i = 0; i < mid; i++) {
        leftHalf[i] = array[i];
    }
    for (int j = mid; j < array.Length; j++) {
        rightHalf[counter] = array[j];
        counter++;
    }
    counter = 0;
    MergeSort(leftHalf);
    MergeSort(rightHalf);
    return SortAndMerge(leftHalf,rightHalf);
}

public Int32[] SortAndMerge(Int32[] left, Int32[] right) {
    Int32[] myResult = new Int32[left.Length+right.Length];
    while (left.Length > 0 || right.Length > 0) {
        if (left.Length > 0 && right.Length > 0)
        {
            if (left[0] <= right[0])
            {
                myResult[myResult.Length] = left[0];
                int toRemoveIndex = Array.IndexOf(left, left[0]);
                left = left.Where((x, y) => y != toRemoveIndex).ToArray();
            }
            else
            {
                myResult[myResult.Length] = right[0];
                int toRemoveIndex = Array.IndexOf(right, right[0]);
                right = right.Where((z, g) => g != toRemoveIndex).ToArray();
            }

        }
        else if (left.Length > 0)
        {
            myResult[myResult.Length] = left[0];
            int toRemoveIndex = Array.IndexOf(left, left[0]);
            left = left.Where((x, y) => y != toRemoveIndex).ToArray();
        }
        else if (right.Length > 0) {
            myResult[myResult.Length] = right[0];
            int toRemoveIndex = Array.IndexOf(right, right[0]);
            right = right.Where((x, y) => y != toRemoveIndex).ToArray();
        }
    }
    return myResult;
}

Answer 1

if (array.Length == 0) return;

这从来都不是真的，因此是异常(exception)，因为你总是像这样创建数组。

Int32[] leftHalf = new Int32[mid+1];

最小长度为 1。

在此处查看正确的合并排序算法。

https://en.wikipedia.org/wiki/Merge_sort#Algorithm