在 C# 中使用哨兵进行合并排序会产生奇怪的输出

Question

我正在尝试使用 C# 中的哨兵实现合并排序算法。

我要排序的数组：

int[] arr = { 9, 8, 7, 6, 5, 4 };

这是我的归并排序函数：

void MergeSort(int[] arr, int lowerIndex, int upperIndex)
        {
            if (upperIndex > lowerIndex)
            {
                int midIndex = (lowerIndex + upperIndex) / 2;
                MergeSort(arr, lowerIndex, midIndex);
                MergeSort(arr, midIndex + 1, upperIndex);
                Merge(arr, midIndex, lowerIndex, upperIndex);

            }
        }

这是我的合并函数：

 void Merge(int[] arr, int midIndex, int lowerIndex, int upperIndex)
        {
            int leftArrayLength = midIndex - lowerIndex + 1;
            int rightArrayLength = upperIndex - midIndex;

            int[] left = new int[leftArrayLength + 1];
            int[] right = new int[rightArrayLength + 1];

            for (int i = 0; i < leftArrayLength; i++)
            {
                left[i] = arr[i];
            }
            for (int j = 0; j < rightArrayLength; j++)
            {
                left[j] = arr[midIndex + j];
            }

            //Sentinels
            left[leftArrayLength] = int.MaxValue;
            right[rightArrayLength] = int.MaxValue;

            int m = 0;
            int n = 0;
            for (int k = lowerIndex; k <= upperIndex; k++)
            {
                if (left[m] <= right[n])
                {
                    arr[k] = left[m];
                    m += 1;
                }
                else
                {
                    arr[k] = right[n];
                    n += 1;
                }

            }
        }

它给出了一个奇怪的输出：

0 0 0 7 0 4

到目前为止，我已经按照 CLRS 中给出的伪代码反复检查了我的实现，但我没有发现我的实现有什么问题。

请告诉我哪里做错了。

Answer 1

您在 left/right 数组初始化中至少有下几个错误：

对于 left 你应该从 lowerIndex:

for (int i = 0; i < leftArrayLength; i++)
{
    left[i] = arr[lowerIndex + i];
}

对于 right 有两个错误 - 1) 数组名称和使用 left 的拼写错误 2) 索引

for (int j = 0; j < rightArrayLength; j++)
{
   right[j] = arr[midIndex + 1 + j];
}

在 C# 中使用哨兵进行合并排序会产生奇怪的输出

Merge Sort using sentinels in C# produces weird outputs

c#

sorting

mergesort