which sorting algorithm is used for std::list's sort member function ?

views:

116

answers:

+2 Q:

which sorting algorithm is used for std::list's sort member function ?

+2 A:

It's implementation defined. However, it must follow these restrictions (§23.2.2.4):

Stable: the relative order of the equivalent elements is preserved.
Complexity: Approximately NlogN comparisons, where N == size().

So it's a stable sort with O(nlog n).

GMan 2010-07-22 07:20:22

Thanks GMan. Which algorithm except merge sort can be used?

Davit Siradeghyan 2010-07-22 07:22:13

@GMan **NEVER** sleeps! :P :D

Gollum 2010-07-22 07:23:40

@Davit: I think Quicksort can be written to be stable, though if I remember correctly it loses some performance that way. (And even though its worse-case is `O(N^2)`, its average case fits the requirements.) You're correct though, I think every implementation I have used uses mergesort. (And for non-stable sorts, Introsort.)

GMan 2010-07-22 07:25:22

Looking at Wikipedia's [stable sorts](http://en.wikipedia.org/wiki/Category:Stable_sorts), I was a bit shocked to discover that Quicksort and Shellsort aren't among them. That really doesn't leave a lot.

Carl Smotricz 2010-07-22 07:25:57

Eugen Constantin Dinca 2010-07-22 07:29:24

ansaurus

tags:

views:

answers:

which sorting algorithm is used for std::list's sort member function ?

related questions