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

Question

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!

The implementation is in the headers, you can see for yourself. My guess would be Introsort, but I haven't checked. — Igor Tandetnik
– Igor Tandetnik, Commented Apr 5, 2014 at 18:41
How do i check the headers, i am just learning this stuff, i don't even know what do you mean by headers. — user2968505
– user2968505, Commented Apr 5, 2014 at 18:46
Write a program that calls sort, run it under debugger, press F7 (Step Into) to step into the actual implementation. Header is the file that you #include. — Igor Tandetnik
– Igor Tandetnik, Commented Apr 5, 2014 at 18:48

Shmil The Cat · Accepted Answer · 2014-04-05 18:42:31Z

6

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

answered Apr 5, 2014 at 18:42

Shmil The Cat

4,6682 gold badges31 silver badges39 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

user2968505 Over a year ago

So say the input is an array of size 5 million, will it use exclusively quicksort ?

Shmil The Cat Over a year ago

@user2968505 it will start w/ quicksort and then for smaller partitions heap sort or insertion sort will be used

Twisted AISTRIKE at 1687989253 Over a year ago

so basically it's a hybrid between the three, right (that source is a little opaque to me since I don't have much experience with C)? Also I dig the pun and am totally going to steal that sometime.

templatetypedef · Accepted Answer · 2014-04-06 00:28:12Z

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:

Run quicksort, stopping on any subrange whose length is below a preset threshold.
If during the quicksort the recursion depth exceeds a certain limit, stop running quicksort and use heapsort instead.
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!

Collectives™ on Stack Overflow

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

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related