Why is Rust's sort much faster than C++'s std::sort?

FWIW both programs are deterministic, and theoretically could be be mostly be done in compile time.

Probably the algorithm. ipnsort is a newly invented algorithm, best in class. It is very unlikely to be due to a fundamental difference between Rust and C++. But of course, the only way to know for sure is to implement the same algorithm in roughly the same code in both languages and benchmark.

Switching to boost pdqsort cut the runtime by ~60% on my machine. And the benchmarks in this document suggest that ipnsort outperforms pdqsort significantly on random inputs - indeed the numbers look pretty similar to what you observed. I don't think there's much to analyze here beyond the algorithmic difference.

Your test is flawed. The simple reason is that you are sorting random data created by two different languages.

Instead, you should create a known set of random values, and feed those same values into both the C++ and Rust version.

Can you add the compilation commands please?

g++ .\test_sort.cpp -O3 -march=native -mtune=native -flto -funroll-loops -fomit-frame-pointer -DNDEBUG
C++: 8577.17 ms
rustc -C opt-level=3 main.rs
Rust: 1379.375 ms

You can't just look at a single example when you do these kinds of comparisons. The scenario that you have here - sort 100,000,000 long values with few duplicates - is not very realistic. Real data that needs sorting usually has way more key duplication in which case the algorithm profile could be completely different.

It is misleading to talk about "C++'s std::sort". There is factor 2.1 in running time whether I compile this same code with g++ or with clang++ -stdlib=libc++. Please call it the std::sort from GCC (or from libstdc++ to be precise).

The Rust looks suspiciously fast for a single threaded sort of 100 million elements to me. Maybe it's multi-threaded? Try running it with time to see the real vs user time. Try inputting the seed value at the command line so the compiler can't just do everything at compile time.