This is the mail archive of the
mailing list for the glibc project.
Carlos O'Donell suggested talking about the code first before stating
with the paperwork. I think this is a sane suggestion.
A few related remarks:
* A badly chosen pivot lowers the number of swaps needed, a really
badly chosen pivot leads to something with a performance comparable
to selection sort.
* The correctness of the median of three selection with detection of
equal elements is not that obvious at first sight, thus I verified
a simpler version, e.g., without a comparison function, using
Frama-C's plugin jessie (not in a very beautiful way, though).
* An earlier version did check if LONG_MAX equals to INT_MAX and set up
the SWAP macro accordingly to also check if int-wise swaps are
possible if they aren't equal.
* The insertion sort at the end (which is btw. with todays cache sizes
hardly a performance gain in comparison to running insertion sort on
small arrays) does not use the tuned SWAP macro and it always adds
about N comparisons.
* The documentation update in my latest commit might contain relevant
* The size of the compiled object could be reduced by moving the
pseudo-median of nine selection to a non-inlined function. In my
tests I could save about 500 byte (after stripping) when compiled
with -Os or -O2.
* Ryan S. Arnold [2011-11-29 09:49 -0600]:
> Patents: This restricts implementation. ?In order for the FSF to
> accept code that utilizes patents I believe the FSF needs to have
> patent cross-licensing (or some other use permit) on file.
Just for completeness, the earlier multi-pivot patent  contains the
| A method for improving the software algorithm in claim 1 involving
| comparing the current pivot about to be partitioned with the last
| pivot, and if these two pivots are equal, pivoting equal records
| remaining in the unpartitioned list between the previous pivot and the
| current pivot. This improvement handles duplicate records during
| runtime and adds very little overhead.
My code also compares pivots to handle equal elements, but both
approaches are completely different (I could be more verbose about this
> Copyright: This denotes ownership of THIS specific block of code/text.
> This indicates who will defend the license in the event of an
> infringement. ?You may release different versions of the code onto the
> net with different copyrights as long as you hold exclusive license to
> the original.
My original version contains the following code (due a lack of
creativity I used the variable names from Bentley and McIlroy):
| if ((r1 = CMP(pa, pd)) > 0) SWAP(pa, pd);
| if ((r2 = CMP(pa, pv)) > 0) SWAP(pa, pv);
The code on github contains this code:
| if ((r1 = ((*cmp) ((void *) hi, (void *) lo, arg))) < 0)
| SWAP (hi, lo);
| if ((r2 = ((*cmp) ((void *) hi, (void *) mid, arg))) < 0)
| SWAP (hi, mid);
There are code blocks that are even more similar and some that are
completely different. I did not assume that these versions really could
count as different work (work might not be the correct term in this
case, but my intention should be clear). If what you wrote above
applies in this case, then we just need to talk about the code and do
the paperwork afterwards.
Notes related to the copyright:
* Although the way I handle multisets is heavily based on Justin Peel's
idea of alternating the side to place the equal elements, I did not
use any of his code or even a similar algorithm.
* The partitioning code is nearly identical to the one used in a paper
"R. Geoff Dromey", but has been written before I read this paper
(there aren't that many ways to implement partitioning).