benchmarking sorting algorithms: std::sort vs my naive radix I'm comparing performance of two sorting algorithms applied to sort integers using google benchmark.
I'm quite surprised by the results so wanted to ask if you see some mistakes in the way I measure the performance. I would expect performance of my naive radix sort to be much worse that std::sort because it is supposed to be bandwidth bound.
#include &lt;benchmark/benchmark.h&gt;

#include &lt;random&gt;
#include &lt;vector&gt; 
#include &lt;array&gt; 
#include &lt;algorithm&gt;

#define TEST_SIZE DenseRange(50000, 1000000, 50000)

class SortingBmk : public benchmark::Fixture
{
public:
    using T = int32_t;
    std::vector&lt;T&gt; m_vals;

    void SetUp(const ::benchmark::State&amp; state)
    {
        const auto n = state.range(0);
        m_vals.resize(n);
        std::iota(m_vals.begin(), m_vals.end(), 0);

        std::random_device rd;
        std::mt19937 g(rd());
        std::shuffle(m_vals.begin(), m_vals.end(), g);
    }

    void TearDown(const ::benchmark::State&amp; state) {}
};

BENCHMARK_DEFINE_F(SortingBmk, StdSort)(benchmark::State&amp; state)
{
    const auto n = state.range(0);

    std::vector&lt;T&gt; values(m_vals.size());
    for (auto _ : state)
    {
        std::copy(m_vals.begin(), m_vals.end(), values.begin());

        std::sort(values.begin(), values.end());
        benchmark::DoNotOptimize(values);
        benchmark::ClobberMemory();
    }
}
BENCHMARK_REGISTER_F(SortingBmk, StdSort)-&gt;Unit(benchmark::kMicrosecond)-&gt;TEST_SIZE;

inline int getBits(SortingBmk::T v, SortingBmk::T i) { return (v &gt;&gt; i)&amp;0b11; }
void radixSort_count(std::vector&lt;SortingBmk::T&gt;&amp; data, std::vector&lt;SortingBmk::T&gt;&amp; buf) {
    const int n = data.size();
    std::array&lt;int, 8&gt; psum = {0};
    constexpr auto sz = sizeof(SortingBmk::T) * 8 - 2;
    for (SortingBmk::T i = 0; i &lt; sz; i += 2) {
        //count sort
        for (int v : data) {
            auto bits = getBits(v, i);
            ++psum[bits];
        }
        for (int i = 1; i &lt; 8; ++i)
            psum[i] += psum[i-1];
        for (int j = n - 1; j&gt;= 0; --j) {
            auto bits = getBits(data[j], i);
            --psum[bits];
            assert(psum[bits] &lt; buf.size());
            buf[ psum[bits] ] = data[j];
        }
        swap(buf, data);
        psum = {0};
    }
}

BENCHMARK_DEFINE_F(SortingBmk, NaiveRadixSort)(benchmark::State&amp; state)
{
    const auto n = state.range(0);

    std::vector&lt;T&gt; values(m_vals.size());
    std::vector&lt;T&gt; buffer(m_vals.size());
    for (auto _ : state)
    {
        std::copy(m_vals.begin(), m_vals.end(), values.begin());

        radixSort_count(values, buffer);
        for (int i = 1; i &lt; values.size(); ++i)
            assert(values[i-1] &lt; values[i]);
        benchmark::DoNotOptimize(values);
        benchmark::ClobberMemory();
    }
}
BENCHMARK_REGISTER_F(SortingBmk, NaiveRadixSort)-&gt;Unit(benchmark::kMicrosecond)-&gt;TEST_SIZE;

BENCHMARK_MAIN();

UPD: X-axis is number of elements in the array, Y-axis is time spend on computations in average for all the times I run the code within for loop. It is in kMicrosecond.
I'm not too surprised to see the radix sort being faster in this use case, 32 bits is very short for a key.
You may want to look at this comparison as well as at the last paragraph of this History section.
About the bench method, I would:

Try with values already sorted.
Try with values sorted in reverse.
Try with multiple sets of random values, each set identified by its seed (so no random seed).
Try with the same as above but with the first half filled with random values and the second half being a copy of the first half.

I would also test the end result, of course.