List<T> sort performance

[Guest]

Hi,

Can I expect a clever sorting algorithm behind the Sort() function for the
List<T> class? Can't find anything on the net that says anything about this.

regards Jesper

 

[Guest]

Hi,

Can I expect a clever sorting algorithm behind the Sort() function for the
List<T> class? Can't find anything on the net that says anything about this.

regards Jesper

Yes. The List<>.Sort method uses Array.Sort, which uses the quick sort
algorithm.

 

[Doug Semler]

Hi,

Can I expect a clever sorting algorithm behind the Sort() function for the
List<T> class? Can't find anything on the net that says anything about
this.

While I wouldn't call quicksort particularly "clever" , I believe that is
the algorithm used to sort List<T>. That being said, quicksort is not so
good (O(n^2)) if the list is sorted or almost sorted unless the pivot point
is randomized (which brings it back to high probability of O(nlgn)), and I
don't know that the Framework's implementation does that. So, if your lists
fall into this "almost sorted" category (and you are either sorting large
lists or sorting lists very often), I would ensure that you profile at some
point to make sure you're not spending an inordinate amount of time sorting.
If that's the case, you're going to want to either keep the list sorted from
the get go or use a different sort implementation.

--
Doug Semler, MCPD
a.a. #705, BAAWA. EAC Guardian of the Horn of the IPU (pbuhh).
The answer is 42; DNRC o-
Gur Hfrarg unf orpbzr fb shyy bs penc gurfr qnlf, abbar rira
erpbtavmrf fvzcyr guvatf yvxr ebg13 nalzber. Fnq, vfa'g vg?

 

[M@Ri0]

Hi,

Can I expect a clever sorting algorithm behind the Sort() function for the
List<T> class? Can't find anything on the net that says anything about this.

regards Jesper

Hi Jesper,

I think you have you'r answere already, but I still want to recommend
you Reflector, in case you don't know it yet.
With that tool you can view the source of any .Net assembly, including
the .Net framework. Sow it can give you
answeres on questions like these.

You can find it at http://www.aisto.com/roeder/dotnet/

Kind regards,

Mario