Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is time complexity of .NET List.sort()

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.

like image 205
Anders Lind Avatar asked Mar 08 '12 02:03

Anders Lind


People also ask

What is the time complexity of list sort?

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).

What is Big O of array sort?

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.

Is C# list sort stable?

Sort isn't stable. However, the LINQ OrderBy methods (and OrderByDescending etc) are stable, which can be very useful.

What does list sort Do C#?

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>)


2 Answers

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.

like image 56
zerkms Avatar answered Sep 23 '22 15:09

zerkms


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"

like image 40
Reed Copsey Avatar answered Sep 21 '22 15:09

Reed Copsey