Should sorting algorithm pass same element in the comparison function

Question

The std::sort of libcxx (llvm version of c++ standard library) calls the comparison predicate with the same element i.e., both the arguments of comparison functor refer to the same position in the sequence to be sorted. A reduced example to illustrate the point.

$ cat a.cc
#include <algorithm>
#include <vector>
#include <cassert>

int main(int argc, char** argv) {
  int size = 100;
  std::vector<int> v(size);

  // Elements in v are unique.
  for (int i = 0; i < size; ++i)
    v[i] = i;

  std::sort(v.begin(), v.end(),
            [&](int x, int y) { assert(x != y); return x < y; });

  return 0;
}

$ clang++ -std=c++11 -stdlib=libc++ a.cc -o a.out
$ ./a.out
a.out: a.cc:14: auto main(int, char **)::(anonymous class)::operator()(int, int) const: Assertion `x != y' failed.
./go.sh: line 5: 19447 Aborted                 (core dumped) ./a.out

Works fine with libstdc++.

$ clang++ -std=c++11 -stdlib=libstdc++ a.cc -o a.out
$ ./a.out

Is this okay to call the comparison function with same element. Isn't this redundant.

Adinaadine

What do you mean by "is this okay"? Are you asking if it's allowed by the standard? – Landlocked

I don't think standard has any such requirement, I was mostly interested from an algorithmic point of view as to why would anyone call the comparison function with same element. Does that make sorting faster by any chance, or it is just a bug. – Adinaadine

FYI, there is a but report (not verified though) at llvm.org/bugs/show_bug.cgi?id=20837 – Adinaadine

@a.k.: i don't believe the statement that sort cannot be O(n log n) if it occasionally compares an element with itself. If it does that once per partition call, it incurs an expected O(n) additional comparisons, which certainly does not change O(n log n) into O(n^2) – Joule

quicksort is O(n^2) in the worst case by definition. That is a different discussion altogether. I was referring the comment #6, llvm.org/bugs/show_bug.cgi?id=20837#c6. Sorry for the confusion – Adinaadine

@a.k.: yes, me too. That is the comment in which it is alleged that the algo cannot be O(n log n) if it ever compares an element with itself. That is not true; using a self-test as a guard adds an O(n) term so it is not the cause of O(n^2) behaviour (and eliminating it does not fix the worst case either). – Joule

Why wouldn't this be implemented as a one time check on the comparator, and perhaps only if compiled in "debug" mode (as opposed to "release" mode)? – Sanjak

Answer 1

I can speak with some authority on this question as I'm the one who wrote this code.

Here is the comparison which is asserting in your example:

https://github.com/llvm-mirror/libcxx/blob/master/include/algorithm#L3994-L3995

As the link is likely to go stale (point to the wrong line) as time goes on, I'll also quote the code here:

            // __m still guards upward moving __i
            while (__comp(*__i, *__m))
                ++__i;

This is known as an "unguarded" loop because there is no check for the iterator __i running off the end of the sequence as it is incremented. The reason this works is because an invariant of this algorithm is that at this point it is known that __i <= __m (which is also in a comment 3 lines above this quote).

If you look at the code above this quote, you will see these comments:

    // The search going up is known to be guarded but the search coming down isn't.
    // Prime the downward search with a guard.

So before we get to this point, a guarded search down the sequence is done. That is, this test:

if (__i == --__j)

After this test finds the lower guard, the algorithm then jumps to the unguarded loops which have only one test per iteration, whereas otherwise there would be two tests per iteration (a test on the iterator and a test on the dereferenced value of the iterator).

The use of "unguarded loops" is the cause of an element being compared with itself. During development I measured that the cost of the one extra comparison in the loop was a better deal than including two comparisons per iteration in the loop.

Of course this is an engineering tradeoff. If the comparison function turned out to be horribly expensive compared to the cost of comparing the iterators themselves, one could come to a different conclusion.

This answer is completely consistent with rici's answer which is also correct (and I've upvoted it). I added my voice as I could drop the "presumably" and point to specific lines of code in the algorithm.

Wintery

Thanks for the answer, I still wonder if this is a good idea because, IIUC, at a later point, it even calls swap on same element. Moreover, this sort algorithm is O(n^2) llvm.org/bugs/show_bug.cgi?id=20837, standard requires O(nlogn). This is not my question but I mentioned this as you are the original author of this algorithm. – Adinaadine

The O(N^2) issue is separable. All that needs to be done is track qsort depth and switch to heap sort when a limit is reached. – Wintery

Answer 2

Presumably, in the opinion of the standard-library authors, it is faster to do a test which is guaranteed to return false than to constantly check for equal indices as well as comparing elements. This might come about because the pivot element is used as a loop sentinel.

It is certainly permitted for the comparison function to be called in this way, and the assert in your code is not permitted.

Joule

Why would the assert not be permitted? – Landlocked

But if the comparison function is less_equal<T>, then it would return true when both the arguments are same, in that case the function would 'swap' same elements, or at least call the swap routine. – Adinaadine

@A.K.: less_equal is not a valid comparator. – Joule

@benjamin: because the comparator must return true or false. Premature termination is not a permitted result. – Joule

Wow. That is a terrible trade off if you're comparing anything but integers. And a welcome to various subtle bugs. I don't like it. – Athwart