🚀 go-pugleaf

In article <4ghoam$dp4@solutions.solon.com>, seebs@solutions.solon.com (Peter Seebach) writes:

	[qsort problem]

|> To clarify: I believe it is incorrect for the library to do so; although
|> it's pretty tenuous, the "which is called with two arguments that point to
|> the objects being compared" seems to mean that to me.  My rationale is that
|> the compiler *cannot* prove that the objects do not depend on being parts
|> of a larger array.  For instance, consider an array of 200 objects; sort
|> the first 100, with a comparison routine that compares not only the objects,
|> but the objects 100 further in the "real" array.  I believe this to be
|> conforming.

The qsort routine rearranges the array passed to it.  I don't think it
is possible for the comparision function to sort the real array 100 objects
further on in lockstep with the qsort routine, without relying on the
algorithm of qsort---which is implementation defined.  In this
case, the comparision function is not well-defined, since at some call,
a < b, later, a > b.

By the way, what is the relation of the ``quicker sort algorithm'' mentioned
in many manuals to the classic quick sort algorithm?  Is it best-of-three?

Konrad Schwarz