automated sub-string search/replace algorithm...

[Tim Rentsch]

For "convenient" element sizes, Bentley & McIlroy will
copy the pivot element to an outside-the-array temporary and
call the comparator with a pointer to the temporary and a
pointer to an in-the-array element. IIRC, this makes some of
their array rearrangements simpler.

As far as I can see, the only thing a comparator can do with
the 7.20.5p2 guarantee that it cannot do with B&Mc is calculate
the array indices of the two arguments, or use <,<=,>=,> on the
pointers, or equivalent. But I can't imagine a comparator that
could do so usefully, given that the array may get rearranged both
before and after each comparator call. So I don't understand why
7.20.5p2 is a requirement. For bsearch(), yes, just possibly, but
for qsort()? I don't get it.

I suspect this provision is included to avoid any difficulties
regarding alignment. If other memory (besides array elements) may be
used, the alignment conditions for that memory have to be specified,
and that isn't so easy to do. Furthermore the implementation may not
have enough information available to align the "other memory"
properly. For example, suppose we have an implementation where the
maximum alignment is 8, but a program, using platform-specific code,
creates an array whose element alignments are 32 (to coincide with
cache lines or device registers or something). There is no way for
qsort to get suitably aligned "other memory", since there isn't any
way of knowing what that alignment is (and may be even more stringent
than the most restrictive alignment that the implementation itself
uses). The easiest and most obvious way to avoid all these problems
is to use just the original array element objects when calling the
user-supplied comparison function.