如何重构此例程以避免使用递归?

作为一个起点,我将删除您的特殊情况 Count == 1 -它们可以由更一般(当前递归)的情况来处理。

这个 if (sLeft.Count > 1 && sRight.Count == 0) 将 从未 因为你检查过 sRight.Count == 0 在开始时-因此此代码将永远无法访问并且是多余的。

最后,不要递归(在这种情况下,这是非常昂贵的,因为您创建的新列表的数量-每个元素一个!)我会在你的 else (实际上,这可以替代整个方法):

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

while (sLeft.Count > 0 && sRight.Count > 0)
{
    if (sLeft[0] <= sRight[0])
    {
        list.Add(sLeft[0]);
        sLeft.RemoveAt(0);
    }
    else
    {
        list.Add(sRight[0]);
        sRight.RemoveAt(0);
    }
}

// one of these two is already empty; the other is in sorted order...
list.AddRange(sLeft);
list.AddRange(sRight);
return list;

(理想情况下,我将重构此项以对每个列表使用整数索引,而不是使用 .RemoveAt ,因为循环遍历列表比销毁列表更具性能,而且保持原始列表的完整性可能很有用。不过,这仍然比原来的代码更有效!)

合并两个排序列表可以在o(n)中完成。

List<int> lList, rList, resultList;
int r,l = 0;

while(l < lList.Count && r < rList.Count)
{
  if(lList[l] < rList[r]
    resultList.Add(lList[l++]);
  else
    resultList.Add(rList[r++]);
}
//And add the missing parts.
while(l < lList.Count)
  resultList.Add(lList[l++]);
while(r < rList.Count)
  resultList.Add(rList[r++]);

我的看法是:

private static List<int> MergeSortedLists(List<int> sLeft, List<int> sRight)
{
    List<int> result = new List<int>();
    int indexLeft = 0;
    int indexRight = 0;

    while (indexLeft < sLeft.Count || indexRight < sRight.Count)
    {
        if (indexRight == sRight.Count ||
            (indexLeft < sLeft.Count && sLeft[indexLeft] < sRight[indexRight]))
        {
            result.Add(sLeft[indexLeft]);
            indexLeft++;
        }
        else
        {
            result.Add(sRight[indexRight]);
            indexRight++;
        }
    }
    return result;
}

如果我必须用手做,我会做什么。=)

你真的确定你的代码是有效的吗?如果不测试它,我可以看到以下内容:

...
else if (sLeft.Count > 1 && sRight.Count == 0)  //<-- sRight is empty
{
    for (int i=0; i<sLeft.Count; i++)
    {
        if (sRight[0] <= sLeft[i]) //<-- IndexError?
        {
            sLeft.Insert(i, sRight[0]);
            return sLeft;
        }
    }
    sLeft.Add(sRight[0]);
    return sLeft;
}
...

你也在要求不同的方法。根据使用情况,我可以做如下操作。下面的代码比较懒惰,因此它不会一次对整个列表进行排序,而是只在请求元素时进行排序。

class MergeEnumerable<T> : IEnumerable<T>
    {
        public IEnumerator<T> GetEnumerator()
        {
            var left = _left.GetEnumerator();
            var right = _right.GetEnumerator();
            var leftHasSome = left.MoveNext();
            var rightHasSome = right.MoveNext();
            while (leftHasSome || rightHasSome)
            {
                if (leftHasSome && rightHasSome)
                {
                  if(_comparer.Compare(left.Current,right.Current) < 0)
                  {
                    yield return returner(left);
                  } else {
                    yield return returner(right);
                  }
                }
                else if (rightHasSome)
                {
                    returner(right);
                }
                else
                {
                    returner(left);
                }
            }
        }

        private T returner(IEnumerator<T> enumerator)
        {
            var current = enumerator.Current;
            enumerator.MoveNext();
            return current;
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return ((IEnumerable<T>)this).GetEnumerator();
        }

        private IEnumerable<T> _left;
        private IEnumerable<T> _right;
        private IComparer<T> _comparer;

        MergeEnumerable(IEnumerable<T> left, IEnumerable<T> right, IComparer<T> comparer)
        {
            _left = left;
            _right = right;
            _comparer = comparer;
        }
    }

编辑: 这基本上与Sergey Osypchuk相同,他只看排序时从头到尾的意志是最快的,但是由于提前排序整个列表的事实,延迟也会更高。因此,正如我所说的,根据使用情况,我可能会采用这种方法,另一种方法是类似于Sergey Osypchuk的方法。

通常可以使用堆栈而不是递归

合并列表(理论上,输入列表是预先排序的)排序可以通过以下方式实现:

List<int> MergeSorting(List<int> a, List<int> b)
    {
        int apos = 0;
        int bpos = 0;
        List<int> result = new List<int>();
        while (apos < a.Count && bpos < b.Count)
        {
            int avalue = int.MaxValue;
            int bvalue = int.MaxValue;
            if (apos < a.Count)
                avalue = a[apos];
            if (bpos < b.Count)
                bvalue = b[bpos];
            if (avalue < bvalue)
            {
                result.Add(avalue);
                apos++;
            }
            else
            {
                result.Add(bvalue);
                bpos++;
            }
        }
        return result;
    }

如果您从未排序的列表开始,则需要使用上面的函数按排序的子序列对其进行拆分,然后将其变为褐色。

我从不使用递归进行合并排序。您可以对输入进行迭代传递,利用这样一个事实:排序后的块大小在每次合并传递中都会翻倍。跟踪每个输入列表中的块大小和已处理项目的计数;当它们相等时,列表将耗尽。当两个列表都用尽时,您可以继续下一对块。当块大小大于或等于输入大小时,就完成了。

编辑: 由于我的误解,我之前留下的一些信息是不正确的-C中的列表类似于数组,而不是链接列表。我很抱歉。