如何实现适配自定义集合与数组的泛型归并排序函数？

我有一个名为CustomList的自定义类，功能类似数组但支持动态扩容。我希望实现一个MergeSort函数，能同时处理CustomList和标准数组。

我的尝试代码 #

Sorter类实现 #

public class Sorter<T> where T : IEnsemble<T>
{
    public static IEnsemble<T> MergeSort(IEnsemble<T> array)
    {
        IEnsemble<T> res;
        if (array.Length > 1)
        {
            IEnsemble<T> left = MergeSort(array[0..(array.Length / 2)]);
            IEnsemble<T> right = MergeSort(array[(array.Length / 2)..]);
            res = MergeSort(left, right);
            return res;
        }
        else { return array; }

    }

    public static IEnsemble<T> MergeSort(IEnsemble<T> left, IEnsemble<T> right)
    {
        int leftPointer = 0;
        int rightPointer = 0;
        IEnsemble<T> res = new IEnsemble<T>(left.Length + right.Length);
        while (leftPointer < left.Length || rightPointer < right.Length)
        {
            if (rightPointer == right.Length || (leftPointer < left.Length && left[leftPointer].CompareTo(right[rightPointer]) < 0))
            {
                res[leftPointer + rightPointer] = left[leftPointer];
                leftPointer++;
            }
            else
            {
                res[leftPointer + rightPointer] = right[rightPointer];
                rightPointer++;
            }
        }
        return res;
    }
}

IEnsemble接口定义 #

public interface IEnsemble<T>
{
    T this[int i] { get; set; }
    IEnsemble<T> this[Range range] { get; }
    int Length { get; }
}

遇到的问题 #

• 范围操作返回的是接口而非具体实现类，不确定是否会引发问题；
• 代码中IEnsemble<T> res = new IEnsemble<T>(left.Length + right.Length);无法运行，因为接口不能被实例化。

核心疑问 #

我想创建一个能同时支持自定义集合类（带索引和范围操作）和标准数组的泛型归并排序函数，这是否可行？如果可行，该怎么实现？

完全可行，核心是解决接口不能实例化的问题，同时兼容标准数组和自定义集合。以下是具体实现步骤：

1. 调整接口与约束 #

首先给IEnsemble<T>新增创建实例的方法，同时给元素类型T加上比较约束（归并排序依赖元素比较）；另外需要给标准数组做接口适配，因为原生数组不实现自定义接口。

调整后的IEnsemble接口 #

public interface IEnsemble<T> where T : IComparable<T>
{
    T this[int index] { get; set; }
    IEnsemble<T> this[Range range] { get; }
    int Length { get; }
    // 新增：创建指定长度的集合实例
    IEnsemble<T> CreateInstance(int length);
}

标准数组的接口适配类 #

创建包装类让数组实现IEnsemble<T>：

public class ArrayWrapper<T> : IEnsemble<T> where T : IComparable<T>
{
    private readonly T[] _array;

    public ArrayWrapper(T[] array) => _array = array;

    public T this[int index]
    {
        get => _array[index];
        set => _array[index] = value;
    }

    public IEnsemble<T> this[Range range]
    {
        get
        {
            var (offset, length) = range.GetOffsetAndLength(_array.Length);
            var subArray = new T[length];
            Array.Copy(_array, offset, subArray, 0, length);
            return new ArrayWrapper<T>(subArray);
        }
    }

    public int Length => _array.Length;

    public IEnsemble<T> CreateInstance(int length)
    {
        return new ArrayWrapper<T>(new T[length]);
    }

    // 方便转换回原生数组
    public T[] ToArray() => _array;
}

让CustomList实现调整后的接口 #

确保你的CustomList<T>实现IEnsemble<T>的所有成员，包括CreateInstance方法：

public class CustomList<T> : IEnsemble<T> where T : IComparable<T>
{
    // 你的原有实现逻辑（动态扩容、元素存储等）
    private T[] _items;
    public int Length => _items.Length;

    // 假设已有指定初始长度的构造函数
    public CustomList(int initialLength)
    {
        _items = new T[initialLength];
    }

    public T this[int index]
    {
        get => _items[index];
        set => _items[index] = value;
    }

    public IEnsemble<T> this[Range range]
    {
        get
        {
            var (offset, length) = range.GetOffsetAndLength(Length);
            var subList = new CustomList<T>(length);
            for (int i = 0; i < length; i++)
            {
                subList[i] = _items[offset + i];
            }
            return subList;
        }
    }

    public IEnsemble<T> CreateInstance(int length)
    {
        return new CustomList<T>(length);
    }
}

2. 修改MergeSort函数 #

现在可以通过CreateInstance方法创建目标类型的实例，替代直接实例化接口的错误写法：

public static class Sorter
{
    public static IEnsemble<T> MergeSort<T>(IEnsemble<T> ensemble) where T : IComparable<T>
    {
        if (ensemble.Length <= 1)
            return ensemble;

        int mid = ensemble.Length / 2;
        var left = MergeSort(ensemble[0..mid]);
        var right = MergeSort(ensemble[mid..]);

        return Merge(left, right);
    }

    private static IEnsemble<T> Merge<T>(IEnsemble<T> left, IEnsemble<T> right) where T : IComparable<T>
    {
        int leftPtr = 0, rightPtr = 0, current = 0;
        // 使用左集合的CreateInstance创建结果，保证返回类型与输入一致
        var result = left.CreateInstance(left.Length + right.Length);

        while (leftPtr < left.Length && rightPtr < right.Length)
        {
            if (left[leftPtr].CompareTo(right[rightPtr]) <= 0)
            {
                result[current] = left[leftPtr];
                leftPtr++;
            }
            else
            {
                result[current] = right[rightPtr];
                rightPtr++;
            }
            current++;
        }

        // 处理剩余元素
        while (leftPtr < left.Length)
        {
            result[current] = left[leftPtr];
            leftPtr++;
            current++;
        }

        while (rightPtr < right.Length)
        {
            result[current] = right[rightPtr];
            rightPtr++;
            current++;
        }

        return result;
    }
}

3. 使用示例 #

对标准数组排序 #

int[] arr = { 3, 1, 4, 1, 5, 9 };
var wrapper = new ArrayWrapper<int>(arr);
var sortedWrapper = Sorter.MergeSort(wrapper);
int[] sortedArr = sortedWrapper.ToArray();

对CustomList排序 #

var customList = new CustomList<int> { 5, 2, 7, 1 };
var sortedList = (CustomList<int>)Sorter.MergeSort(customList);

关于范围操作返回接口的问题 #

范围操作返回接口完全没问题，归并排序的递归过程只依赖接口定义的行为（索引访问、长度获取、实例创建），不需要关心具体实现类。只要所有实现类的范围操作都正确返回符合接口要求的实例，就不会有逻辑问题。

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