Menu
What is time complexity of C#'s List<T>.Sort()
I guess it's o(N)
But after I searched a lot, I didn't get any accurate result.
205
Sorting. The Python list sort() has been using the Timsort algorithm since version 2.3. This algorithm has a runtime complexity of O(n. logn).
In general, Big O describes the runtime characteristics of algorithms, so you can't just ask, what is the Big O of a sorted array, it must be some operation on the array. However, you can consider Big O in terms of the space (memory) taken by some data structure.
Sort isn't stable. However, the LINQ OrderBy methods (and OrderByDescending etc) are stable, which can be very useful.
List<T>. Sort() Method is used to sort the elements or a portion of the elements in the List<T> using either the specified or default IComparer<T> implementation or a provided Comparison<T> delegate to compare list elements. There are total 4 methods in the overload list of this method as follows: Sort(IComparer<T>)
http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx
This method uses Array.Sort, which uses the QuickSort algorithm. This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.
On average, this method is an O(n log n) operation, where n is Count; in the worst case it is an O(n ^ 2) operation.
56
From the documentation:
On average, this method is an O(n log n) operation, where n is Count; in the worst case it is an O(n ^ 2) operation.
This is because it uses Quicksort. While this is typically O(n log n), as mentioned on Wikipedia, "Quicksort is often faster in practice than other O(n log n) algorithms"
40
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
