Can std::sort be specialized to use Bubble Sort for int* using as-if rule?

user_2945027 0
Viewed 132

std::sort has complexity requirements, which is O(n log n). Besides common QuickSort or IntroSort, other algorithms would fit it.

Sure Bubble Sort with O(n2) does not fit.

However, if we take a specialization for pointers to int without explicit predicate. The number of iterations or comparisons cannot be observed, as there's no way to specialize operator< or pointer indirection, and user's code is not allowed to specialize std::less for ints, and as the predicate isn't passed, it is std::less/operator<.

So can int* predicate-less version be specialized to use Bubble Sort by some evil implementation of the STL?

This question is similar to Would it be legal to implement overloads of std::sort with radix sort?, but the answer points out that the Radix sort meets the requirements, so it is not what I intend to ask.

The actual intention is if the implementation is allowed to do optimizations, that are worse for complexity, but better for runtime. I want to focus on "if this is allowed" rather than "if this is possible to make faster implementation with worse complexity", that's why I picked Bubble Sort as clearly horrible example.

language-lawyer big-o sorting c++
1 Answers

The number of iterations or comparisons cannot be observed

So? The complexity of algorithms is given by the Standard, not some observer. Whether you can observe such complexity is irrelevant.

25.8.2.1

  1. Complexity: Let N be last - first. O(NlogN) comparisons and projections.

That's pretty clear. On the other hand, bubble sort requires O(n^2), therefore if an implementation were to use Bubble sort, it would not be conforming to the Standard.

I fail to see how as-if rule is relevant at all.

Also note there are overloads with custom Compare functor, in that case the number of comparison can be observed, even for primitive types.

The actual intention is if the implementation is allowed to do optimizations, that are worse for complexity, but better for runtime.

No, the upper bound for std::sort is clear as I stated above. But if through some magic, the compiler can sort in O(1) or not use Compare, it by all means can do that. If the compiler can prove that you cannot observe whether std::sort has been called or not, the as-if rule can kick in here. Very theoretically, if you use std::sort to only find and access the minimum element, the compiler is under this rule allowed to use a simple for loop finding the maximum.

user_76917290
Related