ふあすぷちゃんのをパクったマージソート

msort.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace Test
{
    class Program
    {
        public static LinkedList<T> mergeList<T>(LinkedList<T> lList, LinkedList<T> rList, Comparison<T> cmp)
        {
            var mList = new LinkedList<T>();
            while(lList.Count > 0 && rList.Count > 0)
            {
                var l = lList.First();
                var r = rList.First();
                if(cmp.Invoke(l, r) > 0)
                {
                    mList.AddLast(l); lList.RemoveFirst();
                }
                else
                {
                    mList.AddLast(r); rList.RemoveFirst();
                }
            }
            while(lList.Count > 0)
            {
                mList.AddLast(lList.First());
                lList.RemoveFirst();
            }
            while(rList.Count > 0)
            {
                mList.AddLast(rList.First());
                rList.RemoveFirst();
            }
            return mList;
        }

        public static LinkedList<T> mergeSort<T>(LinkedList<T> list, Comparison<T> cmp)
        {
            if(list.Count <= 1) return list;
            int len = list.Count >> 1;
            return mergeList(mergeSort(new LinkedList<T>(list.Take(len)), cmp), mergeSort(new LinkedList<T>(list.Skip(len).Take(len+1)), cmp), cmp);
        }
 
        public static void Main(string[] args)
        {
            var rand = new Random();

            LinkedList<int> list = new LinkedList<int>(Enumerable.Range(0, 100000).Select(x => rand.Next(1000)).ToList());
            var slist = new List<int>(mergeSort(list, (x, y) => y - x));
        }
    }
}