C#中无需转数组直接对List<IntPoint>实现归并排序

全程直接操作List<IntPoint>实例，不会将整个列表拷贝转换为数组，无额外全量复制开销，同时修复代码中的三处编译错误。

三处编译错误根因及修复 #

• 构造函数报错：C#要求构造函数名必须与所属类名完全一致，原代码误将MergeSort类的构造函数命名为内部比较器类名PointComparer，编译器会将其识别为对PointComparer类型的方法调用从而抛出错误。将构造函数名改回MergeSort即可。
• 临时集合类型转换报错：原代码声明变量类型为List<IntPoint>，但赋值时使用new IntPoint[arraySize]创建数组，List<T>和数组是不同类型，无法隐式转换。这里仅需创建对应合并区间大小的数组作为临时辅助空间即可，属于归并算法必需开销，不涉及原列表的全量转换。
• 比较逻辑报错：AForge的IntPoint结构体本身没有定义Compare实例方法，原代码已经实现了IComparer<IntPoint>接口的比较类，直接调用比较器的Compare方法传入两个待对比的IntPoint实例即可。

修复后完整实现 #

补全了原代码缺失的递归拆分逻辑，同时做了性能优化：比较器使用单例避免重复实例化、临时空间仅分配当前合并区间所需长度，避免空间浪费。

using System;
using System.Collections.Generic;
using AForge;

namespace blobdnm
{
    class MergeSort
    {
        private readonly int _sortLength;
        private readonly List<IntPoint> _source;
        // 复用单例比较器，减少GC开销
        private static readonly PointComparer _comparer = PointComparer.Instance;

        /// <summary>
        /// 归并排序构造函数，初始化后直接完成排序
        /// </summary>
        /// <param name="source">待排序的IntPoint列表</param>
        /// <param name="length">待排序的元素长度</param>
        public MergeSort(List<IntPoint> source, int length)
        {
            _sortLength = length;
            _source = source;
            MergeSort_Recursive(_source, 0, _sortLength - 1);
        }

        /// <summary>
        /// 合并两个有序子区间
        /// </summary>
        private void DoMerge(List<IntPoint> numbers, int left, int mid, int right)
        {
            int elementCount = right - left + 1;
            // 仅分配当前合并区间所需大小的临时数组，无全量拷贝
            IntPoint[] temp = new IntPoint[elementCount];
            int tempPos = 0;
            int leftCursor = left;
            int rightCursor = mid;
            int leftEnd = mid - 1;

            // 按序合并两个子区间
            while (leftCursor <= leftEnd && rightCursor <= right)
            {
                if (_comparer.Compare(numbers[leftCursor], numbers[rightCursor]) <= 0)
                    temp[tempPos++] = numbers[leftCursor++];
                else
                    temp[tempPos++] = numbers[rightCursor++];
            }

            // 拷贝左区间剩余元素
            while (leftCursor <= leftEnd)
                temp[tempPos++] = numbers[leftCursor++];

            // 拷贝右区间剩余元素
            while (rightCursor <= right)
                temp[tempPos++] = numbers[rightCursor++];

            // 将合并结果写回原列表对应位置
            for (int i = 0; i < elementCount; i++)
            {
                numbers[right] = temp[elementCount - 1 - i];
                right--;
            }
        }

        /// <summary>
        /// 递归拆分数组
        /// </summary>
        private void MergeSort_Recursive(List<IntPoint> numbers, int left, int right)
        {
            if (left >= right) return;
            int mid = (left + right) / 2;
            MergeSort_Recursive(numbers, left, mid);
            MergeSort_Recursive(numbers, mid + 1, right);
            DoMerge(numbers, left, mid + 1, right);
        }

        /// <summary>
        /// IntPoint比较器：先按X坐标升序，X相同按Y坐标升序
        /// </summary>
        public class PointComparer : IComparer<IntPoint>
        {
            public static readonly PointComparer Instance = new PointComparer();
            // 私有构造禁止外部实例化
            private PointComparer(){}
            public int Compare(IntPoint a, IntPoint b)
            {
                int xRes = a.X.CompareTo(b.X);
                return xRes != 0 ? xRes : a.Y.CompareTo(b.Y);
            }
        }
    }
}

调用示例 #

// 初始化待排序列表
List<IntPoint> pointList = new List<IntPoint>
{
    new IntPoint(3,2),
    new IntPoint(1,5),
    new IntPoint(1,2),
    new IntPoint(2,4)
};
// 执行排序，排序结果直接修改原列表
_ = new MergeSort(pointList, pointList.Count);

性能说明 #

• 排序过程全程通过List<T>的索引器直接读写原列表元素，没有将整个List<IntPoint>转换为数组的全量拷贝操作，符合性能要求
• 临时数组为归并算法必需的辅助空间，单次合并仅分配当前区间所需大小，整体空间复杂度保持归并排序标准的O(n)
• 比较器采用单例模式，避免排序过程中重复创建比较器实例，减少GC压力

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