The algorithm std::sort uses

[frek]

Hi all,

#include <iostream>
#include <algorithm>
#include <vector>

template<class T>
class myclass {
public:
    bool operator() (T i, T j) { return (i < j); }
};

int main()
{
    myclass<int> ms;
    std::vector<int> vi{ 12, 2, 54 };

    std::sort(vi.begin(), vi.end(), ms);

    for (auto i : vi)
        std::cout << i << ' ';
    std::cout << '\n';

    system("pause");
    return 0;
}

What is actually done on line 16, I mean what two elements are sent to the functor ms from the beginning to end of the container?

[keskiverto]

http://www.cplusplus.com/reference/algorithm/sort/ writes:

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

Sorts the elements in the range [first,last) into ascending order.
The elements are compared using comp.
Equivalent elements are not guaranteed to keep their original relative order

Complexity
On average, linearithmic in the distance between first and last: Performs approximately N*log2(N) (where N is this distance) comparisons of elements, and up to that many element swaps (or moves).

It is not stated what sorting algorithm the std::sort does / has to use, but the functor is used approximately N*log2(N) times.

[JLBorges]

Almost all implementations of the standard C++ library use the introsort algorithm (or some variant of introsort).
https://en.wikipedia.org/wiki/Introsort

[frek]

Thank you, JLBorges. Your answer is what I was looking for.

[frek]

Got back again to this question! Hhhhh :-)

Just to be completely sure I understood the subject properly, we say that sort uses a mixture of algorithms by/called Introsort even if we've supplied the sort predicate with a user-defined functor that just is using the less-than operator?

One side question, what does exist inside the std namespace? Does it only include STL containers and related algorithms?

[JLBorges]

> Introsort even if we've supplied the sort predicate

The standard sort algorithm is a comparison sort; it compares elements to determine their relative order.
The algorithm uses the predicate to perform the comparisons.


> One side question, what does exist inside the std namespace?
> Does it only include STL containers and related algorithms?

The namespace std may also contain template specialisations provided by the user program.
https://eel.is/c++draft/namespace.std#2

[frek]

The algorithm uses the predicate to perform the comparisons.

You mean the Introsort algorithm uses the predicate we've supplied in the code to compare the elements. right?

[JLBorges]

> You mean the Introsort algorithm uses the predicate we've supplied in the code to compare the elements. right?

Right.
And for the overload where we do not provide a predicate, it uses a default (compare elements using operator<);

[frek]

Thank you.