Reopening so we can discuss things further...:
QuickSort is dangerous! Yet, it's definitely faster than MergeSort
for some cases (~20% faster when sorting terms for writing segment, in
quick test I ran on Wikipedia content).
So the core issue is we should not use QS when there's a risk of any
ties, because in that case it can run really slowly or hit infinite
And we (well, Otis; thank you!) found one such place today (where
MultiPhraseQuery sorts its terms) where we could have many ties and
thus run very slowly / hit stack overflow.
I appreciate the motivation for the "safety net", but, it makes me
nervous... because, say we had done this a few months back... then
Otis likely would not have reported the issue? Ie, the
MultiPhraseQuery would run slowly... which could evade detection
(people may just think it's slow).
I prefer brittle fails over silent slowdowns because the brittle fail
gets your attention and you get a real fix in. Silent slowdowns evade
detection. Sort of like the difference between a virus and
Also, what's preventing us from accidentally using QS somewhere in the
future, where we shouldn't? What's going to catch us?
Robert's first patch would catch this and protect us going forward?
Or, maybe we could strengthen that approach and "assert cmp != 0"
inside QS (ie, no ties are allowed to be passed to QS)?
Though, using asserts only is risky, because it could be the
comparator may return 0, but it's just that none of our test cases
Maybe instead we could do this in a type-safe way: make a new
NoTiesComparator whose compare method can only return LESS_THAN or
GREATER_THAN? And then QS would require NoTiesComparator. Could that