lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Stefan Pohl (JIRA)" <>
Subject [jira] [Commented] (LUCENE-4546) SorterTemplate.quicksort incorrect
Date Wed, 07 Nov 2012 16:29:13 GMT


Stefan Pohl commented on LUCENE-4546:

Thanks for the clarification, Uwe!

Out of curiosity and for reference, are there any reasons for the abstraction having to overwrite
setPivot/comparePivot? Using the implementation in my patch would actually allow to get rid
of having to overwrite these methods at all, possibly being faster due to removal of some
calls depending on JVM optimization and possibly being slower due to a few more swaps and
branches in the code. Pure speculation.
> SorterTemplate.quicksort incorrect
> ----------------------------------
>                 Key: LUCENE-4546
>                 URL:
>             Project: Lucene - Core
>          Issue Type: Bug
>          Components: core/other
>    Affects Versions: 3.6.1, 4.0, 4.1
>            Reporter: Stefan Pohl
>            Assignee: Uwe Schindler
>              Labels: patch
>             Fix For: 3.6.1, 4.0, 4.1
>         Attachments:,,
> On trying to use the very useful o.a.l.utils.SorterTemplate, I stumbled upon inconsistent
sorting behaviour, of course, only a randomized test caught this;)
> Because SorterTemplate.quicksort is used in several places in the code (directly BytesRefList,
ArrayUtil, BytesRefHash, CollectionUtil and transitively index and search), I'm a bit puzzled
that this either hasn't been caught by another higher-level test or that neither my test nor
my understanding of an insufficiency in the code is valid;)
> If the former holds and given that the same code is released in 3.6 and 4.0, this might
even be a more critical issue requiring a higher priority than 'major'.
> So, can a second pair of eyes please have a timely look at the attached test and patch?
> Basically the current quicksort implementation seems to assume that luckily always the
median is chosen as pivot element by grabbing the mid element, not handling the case where
the initially chosen pivot ends up not in the middle. Hope this and the test helps to understand
the issue.
> Reproducible, currently failing test and a patch attached.

This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see:

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message