Which type of sorting is used in the std::sort()?

Most implementations of std::sort use quicksort, (or usually a hybrid algorithm like introsort, which combines quicksort, heapsort and insertion sort).

The only thing the standard requires is that std::sort somehow sort the data according to the specified ordering with a complexity of approximately O(N log(N)); it is not guaranteed to be stable. Technically, introsort better meets the complexity requirement than quicksort, because quicksort has quadratic worst-case time.

C++ Standard ISO/IEC 14882:2003

25.3.1.1 sort

template<class RandomAccessIterator>
   void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
   void sort(RandomAccessIterator first, RandomAccessIterator last,
          Compare comp);

1 Effects: Sorts the elements in the range [first, last).

2 Complexity: Approximately N log N (where N == last - first) comparisons on the average.

There is no information about method but complexity is always N log N.

There are three algorithms that are used in MSVC2013 STL, referring to the source code of std::sort.

It is most likely to use QuickSort, or a variation over QuickSort called IntroSort.

If the recursion goes too deep, the HeapSort will be used here.

Otherwise InsertSort will be used.