Why is swap called by std::sort only if my container has more than 32 elements?

Question

Hello I have a simple question:

class A 
{
public:
    A(int);
    A(const A&);
    A& operator=(const A&);
    ~A();
private:
    int* ptr_;

    friend bool operator<(const A&, const A&);
    friend void swap(A&, A&);
};

A::A(int x) : 
    ptr_(new int(x))
{}

A::A(const A& rhs) :
    ptr_(rhs.ptr_ ? new int(*rhs.ptr_) : nullptr)
{}

A& A::operator = (const A & rhs)
{
    int* tmp = rhs.ptr_ ? new int(*rhs.ptr_) : nullptr;
    delete ptr_;
    ptr_ = tmp;

    return *this;
}

A::~A()
{
    delete ptr_;
}

bool operator<(const A& lhs, const A& rhs)
{
    cout << "operator<(const A&, const A&)" << endl;
    return *lhs.ptr_ < *rhs.ptr_;
}

void swap(A& lhs, A& rhs)
{
    cout << "swap(A&, A&)" << endl;
    using std::swap;
    swap(lhs.ptr_, rhs.ptr_);
}

int main()
{

    std::vector<A> v{ 33,32,31,30,29,28,27,26,25,24,23,22, 21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5, 4,3,2,1 };
    std::sort(v.begin(), v.end());

}

With more than 32 elements, the sort calls swap. With 32 elements or less, the elements are still sorted but swap is not called.

I am using MSVC++ 2019 on x64.
When is swap called and when is it not and why? Thank you!
I didn't use swap in copy-assignment only to distinguish between the call to it from sort from the copy-assignment operator.

`std::sort` resorts to insertion sort if the number of elements is 32 or less, and uses quick sort otherwise. — Evg, Dec 24 '19 at 20:37
@Evg Is that a requirement or is that an explanation for this particular context? — François Andrieux, Dec 24 '19 at 20:38
@FrançoisAndrieux, this is an implementation detail of Microsoft standard library. My guess is that this is the reason of the behaviour observed by OP. I'm currently looking into the source code to gain more details. — Evg, Dec 24 '19 at 20:40
Relevant part of the source is: `while (_ISORT_MAX < (_Count = _Last - _First) && 0 < _Ideal)` where `_ISORT_MAX` is given the value of 32. Line 3447 of `` using VS 16.5.0 — ChrisMM, Dec 24 '19 at 20:41
No real quicksort is used in any modern standard libraries in any languages. All use modified mixed versions which only is a quicksort when the number of elements is large enough. For example Java and Python use [Timsort](https://en.wikipedia.org/wiki/Timsort) while .NET framework and GCC's C++ library use [Introsort](https://en.wikipedia.org/wiki/Introsort). libstdc++ and libc++ also use insertion sort for short sequences. See [What algorithms are used in C++11 std::sort in different STL implementations?](https://stackoverflow.com/a/22356687/995714) — phuclv, Dec 25 '19 at 02:08

Evg · Accepted Answer · 2020-07-04T06:03:43.960

Microsoft std::sort implementation looks like this:

const int ISORT_MAX = 32;  // maximum size for insertion sort

template<class RanIt, class Diff, class Pr>
void Sort(RanIt First, RanIt Last, Diff Ideal, Pr Pred)
{
    Diff Count;
    for (; ISORT_MAX < (Count = Last - First) && 0 < Ideal; )
    {   // divide and conquer by quicksort
        pair<RanIt, RanIt> Mid = Unguarded_partition(First, Last, Pred);

        // ...
    }

    if (ISORT_MAX < Count)
    {   // heap sort if too many divisions
        Make_heap(First, Last, Pred);
        Sort_heap(First, Last, Pred);
    }
    else if (1 < Count)
        Insertion_sort(First, Last, Pred);  // small
}

When the range to be sorted has 32 elements or less, Sort uses insertion sort. Insertion sort doesn't use swap in its implementation. Otherwise, divide-and-conquer quick sort is used. In the implementation it calls iter_swap (inside Unguarded_partition), which in turn calls swap:

template<class FwdIt1, class FwdIt2>
void iter_swap(FwdIt1 Left, FwdIt2 Right)
{   // swap *Left and *Right
    swap(*Left, *Right);
}

All these are implementation details. They vary from one standard library implementation to another.

[libcxx](http://llvm.org/svn/llvm-project/libcxx/trunk/include/algorithm) uses insertion sort for sequences of length smaller than 6 or 30 depending on the type. [libstd++](https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/include/bits/stl_algo.h) does that for sequences of 16 elements or less. [What algorithms are used in C++11 std::sort in different STL implementations?](https://stackoverflow.com/q/22339240/995714) — phuclv, Dec 25 '19 at 02:30

Why is swap called by std::sort only if my container has more than 32 elements?

1 Answers1