13

Could anyone please advise when implementing something like IComparable in .NET what sorting algorithm does .NET use to actually sort the underlying data? Also is the algorithm used customizable or selectable?

Maxim Gershkovich
  • 45,951
  • 44
  • 147
  • 243
  • http://stackoverflow.com/questions/204805/which-sorting-algorithm-is-used-by-net-in-icomparer or http://stackoverflow.com/questions/1854604/which-sorting-algorithm-used-in-net-arrays-sort-method-array-sort I'm surprised the 'new question' dialog box didn't show you similar questions when you entered this one. I'm not surprised that someone didn't search before asking. – Kirk Broadhurst May 11 '11 at 03:24
  • 1
    [This has changed](https://msdn.microsoft.com/en-us/library/6tf1f0bc(v=vs.100).aspx) since .NET 4.5: Now Insertion sort for n<16, otherwise starts with Quicksort and switches to Heapsort when the number of partitions (recursion depth?) exceeds 2 * Log^N. Called: [Introsort](https://en.wikipedia.org/wiki/Introsort) – Laoujin Aug 06 '15 at 23:38

2 Answers2

19

There are two biggies.

Array.Sort (which sorts an array in-place) uses an unstable Quicksort.

This is the same implementation used internally by List<T>.Sort, according to the MSDN documentation:

This method uses Array.Sort, which uses the QuickSort algorithm.

The Enumerable.OrderBy<TSource, TKey> method (which sorts a copy of an input sequence) uses a stable Quicksort.

As far as I know, these are the only two sorting implementations in the .NET BCL.

Dan Tao
  • 125,917
  • 54
  • 300
  • 447
  • 5
    Just an FYI... depending on what it is sorting Array.Sort and List.Sort will choose one of 3 algorithms, either insertion sort, heapsort, and quicksort. With quicksort being the fallback if conditions are not best for the other two. Details are in the MSDN documentation documentation for Array.Sort. – Rodney S. Foley Apr 30 '18 at 19:56
5

The MSDN Documentation states that the sorting algorithm used is Quicksort (at least for arrays) - This is not selectable or customizable.

Note that its not the IComparable interface that specifies what sorting method to use, its down to the method or class that is doing the sorting (normally an array or list, but it could be any method), for example its completely possible for arrays and Lists to sort using completely different algorithms (although in reality both use Quicksort)

This means that if you really want to you can implement your own sorting method using an alternative algorithm.

Justin
  • 84,773
  • 49
  • 224
  • 367