c# - 如何在 C# 中修复此合并排序的实现

Question

我已阅读 CLRS 并尝试实现递归归并排序算法。看不到错误是什么，但每次我运行它都会给我一个“索引越界错误”

我现在已经尝试了 5 小时

static public void MergeSort(int[] input, int IndexStanga, int IndexDreapta)
{
    if (IndexStanga < IndexDreapta)
    {
        int IndexMijloc = (IndexDreapta + IndexStanga) / 2;
        MergeSort(input, IndexStanga, IndexMijloc);
        MergeSort(input, IndexMijloc + 1, IndexDreapta);

        Merge(input, IndexStanga, IndexDreapta, IndexMijloc);
    }
}

static public void Merge(int[] input, int stanga, int dreapta, int mijloc)
{
    int lungDR = 0;
    int lunST = 0;
    lungDR = dreapta - mijloc;
    lunST = mijloc - stanga + 1;
    int[] valDreapta = new int[lungDR + 1];
    int[] valStanga = new int[lunST + 1];

    valDreapta[valDreapta.Length - 1] = int.MaxValue;
    valStanga[valStanga.Length - 1] = int.MaxValue;

    int i = 0;
    int j = 0;

    for (i = stanga; i <= mijloc; i++) valStanga[i] = input[i];

    for (i = 0; i < lungDR; i++) { valDreapta[i] = input[i + mijloc + 1]; }

    i = 0;
    j = 0;

    for (int k = 0; k < input.Length; k++)
    {
        if (valStanga[i] <= valDreapta[j]) //error out of bounds 
        {
            input[k] = valStanga[i];
            i++;
        }
        else
        {
            input[k] = valDreapta[j];
            j++;
        }
    }
}

Answer 1

以下评论中指出的修复。将数据从输入移动到 valStanga 的第一个修复。合并回输入的范围的第二个修复。 merge 的参数顺序很不寻常，first，last，middle。通常顺序是第一、中间、最后。

评论:如果要排序的数组包含等于最大整数的元素，程序将出现问题。一次性分配一个工作数组比在每次调用合并时分配新的子数组效率更高。可以通过改变每个递归级别的合并方向来避免复制操作。

    int i = 0;
    int j = 0;

    for (i = 0; i < lungDR; i++) { valDreapta[i] = input[i + mijloc + 1]; }
    for (i = 0; i < lunST; i++) { valStanga[i] = input[i + stanga]; }      // fix

    i = 0;
    j = 0;

    for (int k = stanga; k <= dreapta; k++)                                // fix
    {
        if (valStanga[i] <= valDreapta[j])