C#实现含正负整数的归并排序时陷入无限循环求助

在实现归并排序处理包含正负整数的列表时，出现了列表计数变为0且程序无限循环的问题，相关代码如下：

static void Main(string[] args)
{
    List<int> test = new List<int>();

    List<int> answer = new List<int>();

    test.Add(1);
    test.Add(6);
    test.Add(-2);
    test.Add(323);
    test.Add(32);
    test.Add(-32);
    test.Add(23);
    test.Add(3);
    test.Add(123);
    test.Add(5);

    answer = MSort(test);

    Console.WriteLine(answer);
}
public static List<int> MSort(List<int> points)
{
    List<int> left, right;
    List<int> result = new List<int>(points.Count);

    if (points.Count <= -1) { return points; }

    int midpoint = points.Count / 2;

    left = new List<int>(midpoint);

    if ((points.Count % 2) == 0)
    {
        right = new List<int>(midpoint);
    }
    else { right = new List<int>(midpoint + 1); }

    for (int i = 0; i < midpoint; i++)
    {
        left.Add(points[i]);
        left[i] = points[i];
    }

    int temp = 0;

    for (int j = midpoint; j < points.Count; j++)
    {
        right.Add(points[j]);
        right[temp] = points[j];
    }

    left = MSort(left);
    right = MSort(right);

    return result = Merge(left, right);

}

public static List<int> Merge(List<int> left, List<int> right)
{
    int length = left.Count + right.Count;

    List<int> result = new List<int>(length);

    int leftIndex, rightIndex, resultIndex;
    leftIndex = rightIndex = resultIndex = 0;

    while ((leftIndex < left.Count) || (rightIndex < right.Count))
    {
        if ((leftIndex < left.Count) && (rightIndex < right.Count))
        {
            if (left[leftIndex] <= right[rightIndex])
            {
                result[resultIndex] = left[leftIndex];
                leftIndex++;
                resultIndex++;
            }
            else
            {
                result[resultIndex] = right[rightIndex];
                rightIndex++;
                resultIndex++;
            }
        }
        else if (leftIndex < left.Count)
        {
            result[resultIndex] = left[leftIndex];
            leftIndex++;
            resultIndex++;
        }
        else if (rightIndex < right.Count)
        {
            result[resultIndex] = right[rightIndex];
            rightIndex++;
            resultIndex++;
        }
    }
    return result;
}

核心错误原因分析 #

1. 递归终止条件完全错误
   MSort方法中的终止条件if (points.Count <= -1) { return points; }逻辑完全不成立：列表的Count属性不可能为负数，这个条件永远不会被触发。当递归拆分出Count=0的空列表时，递归会继续执行下去，因为无法触发终止逻辑，最终导致无限循环。

正确的终止条件应该是当列表元素数量小于等于1时停止递归（单个元素本身就是有序的，空列表也无需排序）：

if (points.Count <= 1) { return points; }

2. 空列表触发无限递归
   当原列表被拆分出Count=0的left列表时，由于终止条件失效，MSort会继续对这个空列表进行拆分：

• midpoint = 0 / 2 = 0
• left和right都被初始化为容量0的空列表
• 再次递归调用MSort处理空列表，这个过程会无限重复，因为永远满足不了错误的终止条件。

3. Merge方法的索引赋值错误
   Merge方法中result = new List<int>(length)只是设置了列表的初始容量，此时result的实际元素数量（Count）还是0。直接通过result[resultIndex]赋值会抛出索引越界异常，应该使用result.Add()来添加元素。

4. 拆分列表时的冗余赋值
   在拆分left和right的循环中，left.Add(points[i]);已经将元素添加到列表中，后续的left[i] = points[i];是完全冗余的操作，直接删除即可，right的循环同理。

修正后的关键代码片段 #

MSort方法修正：

public static List<int> MSort(List<int> points)
{
    if (points.Count <= 1) { return points; }

    int midpoint = points.Count / 2;
    List<int> left = points.Take(midpoint).ToList();
    List<int> right = points.Skip(midpoint).ToList();

    left = MSort(left);
    right = MSort(right);

    return Merge(left, right);
}

Merge方法修正：

public static List<int> Merge(List<int> left, List<int> right)
{
    List<int> result = new List<int>();
    int leftIndex = 0, rightIndex = 0;

    while (leftIndex < left.Count && rightIndex < right.Count)
    {
        if (left[leftIndex] <= right[rightIndex])
        {
            result.Add(left[leftIndex]);
            leftIndex++;
        }
        else
        {
            result.Add(right[rightIndex]);
            rightIndex++;
        }
    }

    while (leftIndex < left.Count)
    {
        result.Add(left[leftIndex]);
        leftIndex++;
    }

    while (rightIndex < right.Count)
    {
        result.Add(right[rightIndex]);
        rightIndex++;
    }

    return result;
}

内容的提问来源于stack exchange，提问作者mskr710