Re: List<T> sort performance

"Jesper, Denmark" <JesperDenmark@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote in message news:96DD23D8-E3A1-40D5-93AC-9F5E2465BBB9@xxxxxxxxxxxxxxxx
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?

.

Relevant Pages

  • Re: Ordering Products
    ... > Kay Schluehr wrote: ... >> It would be interesting to examine some sorting algorithms on factor ... >> lists with constrained item transpositions. ... > I think while the built in sort works as a convenience, ...
    (comp.lang.python)
  • Re: Comparison of functions
    ... What is unintuitive is that you can't sort a list ... objects, we're sorting the list. ... Sorting is not numeric comparisons! ... sorting of lists of arbitrary objects: ...
    (comp.lang.python)
  • Re: Would there be support for a more general cmp/__cmp__
    ... Simce programmers familiar with Python understand that < on sets isn't a "real" comparison, they don't expect unique, consistent results from something like sort. ... Since we don't have a total ordering, sorting doesn't has to give ... that all lists should be sortable regardless of whether the objects within them have a total order or not. ... Libraries just choose to impose a category/numbering at the head of the key. ...
    (comp.lang.python)
  • Re: Linux needs to be taught how to count...
    ... Your application lists a directory any ... Wasn't there a kernel patch or option or something which did sort ... Even Nautilus only offers a choice of "sorted" vs. "unsorted". ... since that will change sorting globally across the ...
    (comp.os.linux.questions)
  • Re: Linux needs to be taught how to count...
    ... Your application lists a directory any ... Wasn't there a kernel patch or option or something which did sort ... Even Nautilus only offers a choice of "sorted" vs. "unsorted". ... since that will change sorting globally across the ...
    (comp.os.linux)
Loading