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

Question

So, I noticed that the tree structure took an unusually long sorting space, at first I thought that most of the time was spent repainting the control after adding each sorted element. But in any case, I had the feeling that List<T>.Sort() took longer than reasonably, so I used my own sorting method for comparison. The results were interesting, List<T>.Sort() took ~ 20 times longer, which is the biggest performance frustration I have ever encountered in .NET for such an easy task.

My question is what could be causing this? My guess is the overhead of calling the comparison delegate, which should also call String.Compare() (in the case of sorting strings). Enlarging the list seems to widen the performance gap. Any ideas? I am trying to use .NET classes as much as possible, but in such cases 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

I did not have time to fully test it, because I had a blackout (email from the phone now), but it seems that your code (from Pastebin) sorts the list already ordered several times, so it seems that your algorithm may be faster .. Sort an already sorted list. In the event that the standard .NET implementation is quicksort, this would be natural, since QS has its worst case scenario for already sorted lists.

Answer 2

Answer: This is not so.

I ran the following test in a simple console application, 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: