11th October 2022, 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”

1. Jeffrey W. Baker says:
   October 11, 2022 at 9:26 pm

   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++.

2. George Spelvin says:
   October 12, 2022 at 12:07 am

   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.