C#归并排序实现错误排查：基于Strategy Pattern的作业问题

我需要用策略模式实现冒泡排序、快速排序和归并排序，前两种已经正常工作，但归并排序输入"bonakid"时输出错误结果"abkidon"。要求归并排序沿用现有的ISortStrategy接口，不能修改其他已实现的排序类。以下是我的代码：

class mergeSort : ISortStrategy
{

    public string Sort(string input)
    {
        var result = "";

        int size = (input.Length % 2 == 0) ? input.Length / 2 : (input.Length + 1) / 2;

        if (input.Length > 1)
        {
            char[] left = input.Substring(0, input.Length / 2).ToCharArray();
            char[] right = input.Substring(input.Length / 2, input.Length - (input.Length / 2)).ToCharArray();

            // Sorting two halves recursively
            Sort(left.Length.ToString());
            Sort(right.Length.ToString());

            //merging left and right sublists
            result = merge(input, left, right);
        }

        return result;
    }

    public string merge(string result, char[] left, char[] right)
    {
        int i1 = 0; // indexing  left
        int i2 = 0; // indexing right

        var theString = result;
        var aStringBuilder = new StringBuilder(theString);

        for (int i = 0; i < aStringBuilder.Length; i++)
        {
            if (i2 >= right.Length || (i1 < left.Length && left.GetValue(i1).ToString().CompareTo(right.GetValue(i2).ToString()) < 0))
            {
                aStringBuilder.Remove(i, 1);
                aStringBuilder.Insert(i, left.GetValue(i1).ToString());
                i1++;
            }
            else
            {
                aStringBuilder.Remove(i, 1);
                aStringBuilder.Insert(i, right.GetValue(i2).ToString());
                i2++;
            }
        }

        theString = aStringBuilder.ToString();
        return theString;

    }
}

public interface ISortStrategy
{
    string Sort(string input);
}

问题排查与修正 #

你的归并排序实现存在几个核心逻辑错误，以下是问题点和修正后的代码：

核心问题 #

• 递归调用完全无效：当前递归传入的是子数组长度的字符串（如Sort(left.Length.ToString())），完全没有处理子数组的实际内容，导致左右子串从未被排序。
• 合并逻辑错误：merge方法基于原始输入字符串修改，而非合并已排序的子串，完全违背归并排序的合并逻辑。
• 冗余的字符转换：将char转成string再比较，既低效又容易出错。

修正后的代码 #

class mergeSort : ISortStrategy
{
    public string Sort(string input)
    {
        // 基线条件：长度<=1无需排序，直接返回
        if (input.Length <= 1)
            return input;

        // 分割字符串为左右两部分
        int mid = input.Length / 2;
        string leftSubStr = input.Substring(0, mid);
        string rightSubStr = input.Substring(mid);

        // 递归排序左右子串，拿到排序后的结果
        string sortedLeft = Sort(leftSubStr);
        string sortedRight = Sort(rightSubStr);

        // 合并两个已排序的子串
        return Merge(sortedLeft, sortedRight);
    }

    // 私有合并方法，仅内部调用
    private string Merge(string left, string right)
    {
        StringBuilder sb = new StringBuilder();
        int leftIndex = 0, rightIndex = 0;

        // 双指针遍历合并两个有序字符串
        while (leftIndex < left.Length && rightIndex < right.Length)
        {
            if (left[leftIndex].CompareTo(right[rightIndex]) <= 0)
            {
                sb.Append(left[leftIndex]);
                leftIndex++;
            }
            else
            {
                sb.Append(right[rightIndex]);
                rightIndex++;
            }
        }

        // 追加左子串剩余的字符
        while (leftIndex < left.Length)
        {
            sb.Append(left[leftIndex]);
            leftIndex++;
        }

        // 追加右子串剩余的字符
        while (rightIndex < right.Length)
        {
            sb.Append(right[rightIndex]);
            rightIndex++;
        }

        return sb.ToString();
    }
}

修正说明 #

1. 修复递归逻辑：递归传入左右子串的实际内容，接收排序后的结果，确保子串先被正确排序。
2. 重构合并逻辑：Merge方法直接处理两个已排序的子串，使用双指针法高效合并，最后追加剩余元素，完全符合归并排序的核心逻辑。
3. 简化字符比较：直接使用char类型的CompareTo方法，避免不必要的字符串转换，提升效率。
4. 优化基线条件：直接判断长度<=1时返回，逻辑更清晰简洁。

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