Why is std :: shuffle slower (or even slower) std :: sort?

Question

Consider a simple code that measures the execution time and the number of swaps executed:

#include <iostream>

#include <vector>
#include <random>
#include <chrono>
#include <algorithm>

struct A {
    A(int i = 0) : i(i) {}
    int i;
    static int nSwaps;

    friend void swap(A& l, A& r)
    {
        ++nSwaps;
        std::swap(l.i, r.i);
    }

    bool operator<(const A& r) const
    {
        return i < r.i;
    }
};

int A::nSwaps = 0;

using std::chrono::high_resolution_clock;
using std::chrono::duration_cast;
using std::chrono::milliseconds;


int main()
{
    std::vector<A> v(10000000);

    std::minstd_rand gen(std::random_device{}());
    std::generate(v.begin(), v.end(), [&gen]() {return gen();});

    auto s = high_resolution_clock::now();
    std::sort(v.begin(), v.end());
    std::cout << duration_cast<milliseconds>(high_resolution_clock::now() - s).count() 
        << "ms with " << A::nSwaps << " swaps\n";

    A::nSwaps = 0;
    s = high_resolution_clock::now();
    std::shuffle(v.begin(), v.end(), gen);
    std::cout << duration_cast<milliseconds>(high_resolution_clock::now() - s).count() 
        << "ms with " << A::nSwaps << " swaps\n";
}

The output of the program depends on the compiler and the machine, but they are quite similar in nature. On my laptop with VS2015, I get 1044 ms with ~ 100 million swaps to sort and 824 ms with 10 million swaps for shuffle.

libstd++ lib++ sort (~ 50M), . Rextester : gcc sort 854ms, shuffle 565ms, clang sort 874ms, shuffle 648ms. , ideone coliru, : ideone sort 1181ms, 1292 coliru sort 1157, 1461 .

? 5 10 , ? std::sort, , .. , - std::minstd_rand, . , ?

PS: std::vector<int>

Answer 1

std::random_shuffle :

//random(k) generates uniform random from 0 to k-1 inclusive
for (int i = 1; i < n; i++)
  swap(arr[i], arr[random(i + 1)]);

, :

• .
• swap . , , , .

2, , quicksort, : -.

Answer 2

-, std::sort swap. , swap, ADL. , sort std::rotate, swap, memmove. .

-, , O(N) std::shuffle O(N log N) std::sort. , N (, 2 65 65 ) . N sort , shuffle, .

: , / - ( @stgatilov). . DEMO, std::sort std::shuffle. sort shuffle, 5- .