Which type of sorting is used in the std::sort()?_问答_开发者

Can anyone please tell me that which type of sorting technique (bubble, insertion, selection, quick, merge, count...) is implemented in the std::sort() function defined in th开发者_运维问答e <algorithm> header file?

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.

Probably all implementations of std::sort use introsort (aka introspection sort), a hybrid algorithm that combines quicksort and heapsort. Actually, introsort was particularly invented in 1997 for the purpose of a performant sort implemenation in C++ STL.

The only thing the standard requires is that std::sort somehow sort the data according to the specified ordering with a complexity of O(N log(N)); it is not guaranteed to be stable (there is a separate std::stable_sort algorithms available, if this should be required).

Technically, introsort better meets the complexity requirement than quicksort: This is because heapsort has guaranteed O(N log(N)) complexity in the worst case, whereas quicksort has quadratic worst-case time.

However, heapsort is 'slower' than quicksort in the average case, in the sense that heapsort performs C*N log(N) whereas quicksort has D*N log(n) performance, with D being significantly smaller than C (the numbers C and D are constants). In other words, the per-comparison-overhead of heapsort is higher than the one of quicksort.

To get the best of both worlds, introsort starts with quicksort —a recursive algorithm—, but when recursion depth gets too high (which means it gets into a degenerated worst-case behaviour), it switches to heapsort.

See also the Wikipedia entry for introsort or the original paper from David Musser, who invented introsort particularly for STL.

GCC 9.2.0 libstdc++ source confirming introsort

Others have mentioned introsort, but here is some evidence for libstc++, which is the default C++ implementation on most Linux distros.

libstdc++ is a part of GCC itself, so we will look into GCC source.

libstdc++-v3/include/std/algorithm is the main header and contains:

#include <bits/stl_algobase.h>
#include <bits/stl_algo.h>

Then, bits/stl_algo.h contains the definition of the sort overloads, one of them being:

  /**
   *  @brief Sort the elements of a sequence.
   *  @ingroup sorting_algorithms
   *  @param  __first   An iterator.
   *  @param  __last    Another iterator.
   *  @return  Nothing.
   *
   *  Sorts the elements in the range @p [__first,__last) in ascending order,
   *  such that for each iterator @e i in the range @p [__first,__last-1),  
   *  *(i+1)<*i is false.
   *
   *  The relative ordering of equivalent elements is not preserved, use
   *  @p stable_sort() if this is needed.
  */
  template<typename _RandomAccessIterator>
    inline void
    sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        _RandomAccessIterator>)
      __glibcxx_function_requires(_LessThanComparableConcept<
        typename iterator_traits<_RandomAccessIterator>::value_type>)
      __glibcxx_requires_valid_range(__first, __last);
      __glibcxx_requires_irreflexive(__first, __last);

      std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
    }

so we see that this just does a bunch of sanity checks on the input, and then calls std::__sort which is defined in the same file:

  template<typename _RandomAccessIterator, typename _Compare>
    inline void
    __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
       _Compare __comp)
    {
      if (__first != __last)
    {
      std::__introsort_loop(__first, __last,
                std::__lg(__last - __first) * 2,
                __comp);
      std::__final_insertion_sort(__first, __last, __comp);
    }
    }

and I'll stop here that we have reached an identifier called std::__introsort_loop, the rest of the implementation is on the same file is anyone still has doubts.

It should also be possible to GDB step debug into std::sort without any further setup in Ubuntu 18.04 as mentioned for std::set at: What is the underlying data structure of a STL set in C++?

C++17 parallel sorting

We now also have parallel sorting, so it would be worth looking on how it is done as well: Are C++17 Parallel Algorithms implemented already?

As mentioned in the above answer, the implementation relies on an external library: Intel Thread Building Blocks: https://github.com/intel/tbb

Do you mean std::sort? If so it can be implemented any way they want. Its probably Quick sort but could be radix or something else. As long as it produces you a sorted list in at least O(n log n) the implementation is fine, afaik.

Just some empirical results:

I translated a python script using numpy 1.9.2 sort to C++ using std::sort (VS2008 toolchain).

I only get the same exact results in the python and C++ sides when I use numpy.sort argument kind='mergesort'. I get different relative ordering for elements with same key when kind='quicksort' or kind='heapsort'. So I guess that at least for the version of STL that comes with VS2008 std::sort uses mergesort.