[Bug libc/7018] bug in _quicksort

["ebiggers3 at gmail dot com" <sourceware-bugzilla at sourceware dot org>]

https://sourceware.org/bugzilla/show_bug.cgi?id=7018

Eric Biggers <ebiggers3 at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ebiggers3 at gmail dot com

--- Comment #2 from Eric Biggers <ebiggers3 at gmail dot com> ---
I was surprised no one has looked into this, so I decided to.  My conclusion is
that this is not, in fact, a bug.

The supposedly problematic assignments to 'mid' are used to update the pointer
to the pivot in cases where it was already swapped to a new location.  Since
'mid' is not otherwise used except to access the pivot element, the real
question is whether moving the pivot can invalidate the algorithm.

Unlike in some implementations of quicksort partitioning, in the glibc
implementation the state of the array after partitioning will not necessarily
be two partitions separated by the pivot element.  Instead, the final state
will be either two consecutive nonempty partitions or two nonempty partitions
separated by one element equal to (but not necessarily the same as) the pivot. 
In both cases all elements in the first partition will be less than or equal to
the pivot and all elements in the second partition will be greater than or
equal to the pivot.  The original pivot element may end up anywhere in the
array except the first and last position, but this appears valid in this
implementation.  Furthermore, in both cases, 'left_ptr' ends up pointing to the
first element of the second partition and 'right_ptr' ends up pointing to the
last element of the first partition, so these pointers can be (and are) used to
measure the size of the partitions.  I don't know whether this is really the
"optimal" partitioning algorithm, but it seems valid.  Therefore this bug as
reported appears to be nonexistent.

Note:  No relevant changes were made to the code between the time the bug was
reported and now.

-- 
You are receiving this mail because:
You are on the CC list for the bug.