Which Type of Sorting Is Used in the Std::Sort()

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.

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

The standard doesn't require a particular algorithm, only that it must be stable, and that it complete the sort using approximately N lg N comparisons. That allows, for example, a merge-sort or a linked-list version of a quick sort (contrary to popular belief, quick sort isn't necessarily unstable, even though the most common implementation for arrays is).

With that proviso, the short answer is that in most current standard libraries, std::sort is implemented as a intro-sort (introspective sort), which is basically a Quicksort that keeps track of its recursion depth, and will switch to a Heapsort (usually slower but guaranteed O(n log n) complexity) if the Quicksort is using too deep of recursion. Introsort was invented relatively recently though (late 1990's). Older standard libraries typically used a Quicksort instead.

stable_sort exists because for sorting array-like containers, most of the fastest sorting algorithms are unstable, so the standard includes both std::sort (fast but not necessarily stable) and std::stable_sort (stable but often somewhat slower).

Both of those, however, normally expect random-access iterators, and will work poorly (if at all) with something like a linked list. To get decent performance for linked lists, the standard includes list::sort. For a linked list, however, there's not really any such trade-off -- it's pretty easy to implement a merge-sort that's both stable and (about) as fast as anything else. As such, they just required one sort member function that's required to be stable.

Which STL container is best for std::sort? (Does it even matter?)

I don't think std::sort works on lists as it requires a random access iterator which is not provided by a list<>. Note that list<> provides a sort method but it's completely separate from std::sort.

The choice of container does matter. STL's std::sort relies on iterators to abstract away the way a container stores data. It just uses the iterators you provide to move elements around. The faster those iterators work in terms of accessing and assigning an element, the faster the std::sort would work.

What algorithms are used in C++11 std::sort in different STL implementations?

Browsing the online sources for libstdc++ and libc++, one can see that both libraries use the full gamut of the well-known sorting algorithms from an intro-sort main loop:

For std::sort, there is a helper routine for insertion_sort (an O(N^2) algorithm but with a good scaling constant to make it competitive for small sequences), plus some special casing for sub-sequences of 0, 1, 2, and 3 elements.

For std::partial_sort, both libraries use a version of heap_sort (O(N log N) in general), because that method has a nice invariant that it keeps a sorted subsequence (it typically has a larger scaling constant to make it more expensive for full sorting).

For std::nth_element, there is a helper routine for selection_sort (again an O(N^2) algorithm with a good sclaing constant to make it competitive for small sequences). For regular sorting insertion_sort usually dominates selection_sort, but for nth_element the invariant of having the smallest elements perfectly matches the behavior of selection_sort.

Should I use sorting algorithms like bubble sort, insertion sort or should I use the inbuilt sort() function in c++ to sort arrays?

Should I use sorting algorithms like bubble sort, insertion sort or should I use the inbuilt sort() function in c++ to sort arrays?

It is your wish. You can use anything. But you need to understand the importance of time and space complexity, your requirement before using any code.

And if I should use sort() function, why do I need to learn other sorting algorithms?

The answer to this is tricky. You need to learn stuff because each sorting algorithm is different on implementation, time and space complexities. For instance, bubble sort runs in O(n^2) time while merge sort takes O(n log n) time.
while space taken by bubble sort is O(1) and merge sort takes O(n) space.In terms of code complexity, you could write a bubble sort snippet in 5 minutes while merge sort could take 30 minutes.

I'm not understanding what is the use of such algorithms if there is an inbuilt sort function, do they have something special?

Yes they do. It is to do with requirements. Today , you might not need a space effecient algorithm. But when such a case arises, you may need to prefer a particular algorithm over the other. In general, you learn these concepts just to understand how the current algorithms have been developed.

Is std::sort optimized for sorting small amount of items too?

Looking at the code of std::sort in STL of MSVC++2013, it uses insertion sorting for 7 items.

Some comments suggested to use sorting networks. Sorting networks for small number of items (up to 32) can be generated here. Particularly, for sorting 7 items without parallelism the fastest algorithm seems this . According to the experiments here, the fastest SWAP macro implementation is:

#define min(x, y) (x<y?x:y)
#define max(x, y) (x<y?y:x) 
#define SWAP(x,y) { \
    const int a = min(d[x], d[y]); \
    const int b = max(d[x], d[y]); \
    d[x] = a; d[y] = b; }

The sorting-network code for 7 items would be:

template<typename T> void sort7(T* d)
{
    SWAP(0, 1);
    SWAP(2, 3);
    SWAP(0, 2);
    SWAP(1, 3);
    SWAP(1, 2);
    SWAP(4, 5);
    SWAP(4, 6);
    SWAP(5, 6);
    SWAP(0, 4);
    SWAP(1, 5);
    SWAP(1, 4);
    SWAP(2, 6);
    SWAP(3, 6);
    SWAP(2, 4);
    SWAP(3, 5);
    SWAP(3, 4);
} 

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

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

std::list sort algorithm runtime

If every element is within k positions of its proper place, then insertion sort will take less than kN comparisons and swaps/moves. It's also very easy to implement.

Compare this to the N*log(N) operations required by merge sort or quick sort to see if that will work better for you.

Sorting an std::list that contains structs

You should give a look to std::sort. (https://en.cppreference.com/w/cpp/algorithm/sort) There is multiple definitions of that function, and one where you can specify on what you want to sort.

Also, give a look to that post, I think it's what you need : https://stackoverflow.com/a/21234017/6663947

Edit :

thats an exemple of comparator :

sList.sort([](const student & a, const student & b) { return a.id < b.id; });

I did not tried it, but it should look like it. Also, this is for c++11

Hope it helps!

---

Related Topics