[LUCENE-3054] SorterTemplate.quickSort stack overflows on broken comparators that produce only few disticnt values in large arrays

• Type: Task
• Status: Closed
• Priority: Critical
• Resolution: Fixed
• Affects Version/s: 3.1
• Fix Version/s: 3.2, 4.0-ALPHA
• Lucene Fields: New, Patch Available
• Assignee: Uwe Schindler
• Reporter: Robert Muir
• Created: 29/Apr/11 17:45
• Updated: 28/Aug/22 12:45
• Resolved: 03/May/11 13:19

Description

Looking at Otis's sort problem on the mailing list, he said:

* looked for other places where this call is made - found it in
MultiPhraseQuery$MultiPhraseWeight and changed that call from
ArrayUtil.quickSort to ArrayUtil.mergeSort
* now we no longer see SorterTemplate.quickSort in deep recursion when we do a
thread dump

I thought this was interesting because PostingsAndFreq's comparator
looks like it needs a tiebreaker.

I think in our sorts we should add some asserts to try to catch some of these broken comparators.