, 2 min read

# The number of comparisons needed to sort a shuffled array: qsort versus std::sort

2 thoughts on “The number of comparisons needed to sort a shuffled array: qsort versus std::sort”

, 2 min read

2 thoughts on “The number of comparisons needed to sort a shuffled array: qsort versus std::sort”

Jeffrey W. Bakersays:For whatever it’s worth, I get the same numbers you get from GCC 9 when using LLVM 15 and 14 on x86-64 Linux, with either GNU libstdc++ or LLVM libc++.

George Spelvinsays:That’s very interesting. The example code uses pseudorandom doubles for input, so the input is in random order and duplicates are vanishingly unlikely.

The two obvious suspects are:

1) The

`std::sort`

template code is inline expanded with specialized compare and swap operations. In return for this optimization opportunity, the code might have to use a more concise algorithm than the out-of-line`qsort()`

. In particular, median-of-medians pivot choosing code can be voluminous and might be omitted from a template implementation.2) There is a semantic difference:

`std::sort`

takes a two-way “<" predicate, while`qsort()`

takes a three-way “” comparison operator. There might be some extra comparisons in`std::sort`

to detect duplicate values, which can cause asymmetric pivot problems in quicksort.