Why is List<string>.Sort() slow?

Question

So I noticed that a treeview took unusually long to sort, first I figured that most of the time was spent repainting the control after adding each sorted item. But eitherway I had a gut feeling that List<T>.Sort() was taking longer than reasonable so I used a custom sort method to benchmark it against. The results were interesting, List<T>.Sort() took ~20 times longer, that's the biggest disappointment in performance I've ever encountered in .NET for such a simple task.

My question is, what could be the reason for this? My guess is the overhead of invoking the comparison delegate, which further has to call String.Compare() (in case of string sorting). Increasing the size of the list appears to increase the performance gap. Any ideas? I'm trying to use .NET classes as much as possible but in cases like this I just can't.

Edit:

    static List<string> Sort(List<string> list)
    {
        if (list.Count == 0)
        {
            return new List<string>();
        }

        List<string> _list = new List<string>(list.Count);
        _list.Add(list[0]);

        int length = list.Count;

        for (int i = 1; i < length; i++)
        {
            string item = list[i];

            int j;

            for (j = _list.Count - 1; j >= 0; j--)
            {
                if (String.Compare(item, _list[j]) > 0)
                {
                    _list.Insert(j + 1, item);

                    break;
                }
            }

            if (j == -1)
            {
                _list.Insert(0, item);
            }
        }

        return _list;
    }

Answer 1

Answer: It's not.

I ran the following benchmark in a simple console app and your code was slower:

    static void Main(string[] args)
    {
        long totalListSortTime = 0;

        long totalCustomSortTime = 0;

        for (int c = 0; c < 100; c++)
        {
            List<string> list1 = new List<string>();
            List<string> list2 = new List<string>();

            for (int i = 0; i < 5000; i++)
            {
                var rando = RandomString(15);
                list1.Add(rando);
                list2.Add(rando);
            }

            Stopwatch watch1 = new Stopwatch();
            Stopwatch watch2 = new Stopwatch();

            watch2.Start();
            list2 = Sort(list2);
            watch2.Stop();
            totalCustomSortTime += watch2.ElapsedMilliseconds;

            watch1.Start();
            list1.Sort();
            watch1.Stop();
            totalListSortTime += watch1.ElapsedMilliseconds;



        }

        Console.WriteLine("totalListSortTime = " + totalListSortTime);
        Console.WriteLine("totalCustomSortTime = " + totalCustomSortTime);

        Console.ReadLine();
    }

Result:

Answer 2

I haven't had the time to fully test it because I had a blackout (writing from phone now), but it would seem your code (from Pastebin) is sorting several times an already ordered list, so it would seem that your algorithm could be faster to...sort an already sorted list. In case the standard .NET implementation is a Quick Sort, this would be natural since QS has its worst case scenario on already sorted lists.