Which sorting algorithm is used by Microsoft's STL::list::sort()?

Question

Note: I accidentally posted this question without specifying which STL implementation I was using, and I felt it can't really be updated since it would render most of its answers obsolete.

So, the correct question goes - which sorting algorithm is used in the below code, assuming I'm using the STL library of Microsoft Visual C++?:

list<int> mylist;

// ..insert a million values

mylist.sort();

Answer 1

To my knowledge it is Introsoft: http://en.wikipedia.org/wiki/Introsort

Answer 2

At least in recent versions (e.g. VC++ 9.0/VS 2008) MS VC++ uses a merge-sort.

Answer 3

Just so you don't have to rely on second hand information, the the sort code is right in the list header - it's about 35 lines.

Appears to be a modified iterative (non-recursive) merge sort with up to 25 bins (I don't know if there's a particular name for this variant of merge sort).

Answer 4

STL that came with MS VC6 was the P. J. Plauger's version of the library (Dinkumware) and it used merge-sort in std::list<>::sort(). I dont know about later versions of MS's package.