我型长（升序）的数数排序的序列，并希望生成包含在同一个订单中所有的元素一个主序列。我寻找最有效的排序算法来解决这个问题。我针对C＃.NET 4.0中，因此也欢迎针对并行的想法。

I have several sorted sequences of numbers of type long (ascending order) and want to generate one master sequence that contains all elements in the same order. I look for the most efficient sorting algorithm to solve this problem. I target C#, .Net 4.0 and thus also welcome ideas targeting parallelism.

下面是一个例子： S1 = 1,2,3,5,7,13 S2 = 2,3,6 S3 = 4,5,6,7,8 所得序列= 1,2,2,3,3,4,5,5,6,6,7,7,8,13

Here is an example: s1 = 1,2,3,5,7,13 s2 = 2,3,6 s3 = 4,5,6,7,8 resulting Sequence = 1,2,2,3,3,4,5,5,6,6,7,7,8,13

编辑：当有两个（或更多）相同的值则顺序这两个（或更多个）也没有关系

When there are two (or more) identical values then the order of those two (or more) does not matter.

推荐答案

更​​新：

原来，所有的算法，...这是仍然较快的简单方法：

Turns out that with all the algorithms... It's still faster the simple way:

private static List<T> MergeSorted<T>(IEnumerable<IEnumerable<T>> sortedBunches)
{
    var list = sortedBunches.SelectMany(bunch => bunch).ToList();

    list.Sort();

    return list;
}

和遗留的目的...

下面是最后的版本，优先考虑：

Here is the final version by prioritizing:

    private static IEnumerable<T> MergeSorted<T>(IEnumerable<IEnumerable<T>> sortedInts) where T : IComparable<T>
    {
        var enumerators = new List<IEnumerator<T>>(sortedInts.Select(ints => ints.GetEnumerator()).Where(e => e.MoveNext()));

        enumerators.Sort((e1, e2) => e1.Current.CompareTo(e2.Current));

        while (enumerators.Count > 1)
        {
            yield return enumerators[0].Current;

            if (enumerators[0].MoveNext())
            {
                if (enumerators[0].Current.CompareTo(enumerators[1].Current) == 1)
                {
                    var tmp = enumerators[0];
                    enumerators[0] = enumerators[1];
                    enumerators[1] = tmp;
                }
            }
            else
            {
                enumerators.RemoveAt(0);
            }
        }

        do
        {
            yield return enumerators[0].Current;
        } while (enumerators[0].MoveNext());
    }