CODEWITHSUNDEEP
algorithmsortingvisual-c++stl
user2968505
user2968505

Reputation: 445

What sorting algorithm does visual c++ use in std::sort

I've been searching for a while now, but i can't find what algorithm does visual c++ use for the std::sort function, i know the GNU Standard C++ library uses Introsort, but there doesn't seem to be any sources saying which one Microsoft's visual c++ use!

Upvotes: 5

Views: 2548

Answers (2)

templatetypedef
templatetypedef

Reputation: 372942

If I remember correctly, the implementation uses an algorithm called introsort, a hybrid of quicksort, heapsort, and insertion sort. The basic idea is as follows:

  1. Run quicksort, stopping on any subrange whose length is below a preset threshold.
  2. If during the quicksort the recursion depth exceeds a certain limit, stop running quicksort and use heapsort instead.
  3. At the end, run insertion sort on the whole array. Since the elements are all close to their final positions, this will only take time O(n).

The advantage of introsort is that in the common case, it uses quicksort (very fast) until insertion sort is better, getting the advantages of both. In the event that the quicksort starts to degenerate, it uses heapsort, which is O(n log n) worst-case but slightly slower than quicksort on average, to guarantee O(n log n) worst-case runtimes. Overall, it's a very fast, in-place sorting algorithm.

Hope this helps!

Upvotes: 4

Shmil The Cat
Shmil The Cat

Reputation: 4668

Use the source Luke :) its quicksort (MSVC 2013) or some times heap sort or even insertion sort (based on the size of the container)

template<class _RanIt,
    class _Diff> inline
    void _Sort(_RanIt _First, _RanIt _Last, _Diff _Ideal)
    {   // order [_First, _Last), using operator<
    _Diff _Count;
    for (; _ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal; )
        {   // divide and conquer by quicksort

Upvotes: 6

Related Questions