CODEWITHSUNDEEP
c#sortingsortedlist
William
William

Reputation: 3395

SortedList Performance - how does the sorted list sort itself?

I am trying to find out more details about the sorted list so that I can analyze whether it will perform like I need it to in several specific situations.

Does anyone know the specific sorting algorithm that it uses to sort its elements?

Upvotes: 0

Views: 2019

Answers (1)

Reed Copsey
Reed Copsey

Reputation: 564413

SortedList<T,U> uses an array internally for its keys, and performs the "sort" by inserting the items on Add in the correct order. When you call Add with a new item, it does a Array.BinarySearch with an Array.Insert.

This is why it has these characteristics:

This method is an O(n) operation for unsorted data, where n is Count. It is an O(log n) operation if the new element is added at the end of the list. If insertion causes a resize, the operation is O(n).

Upvotes: 7

Related Questions