[LUCENE-9024] Optimize IntroSelector for worst case

• Type: Improvement
• Status: Closed
• Priority: Minor
• Resolution: Fixed
• Fix Version/s: 8.4
• Component/s: core/other
• Labels: pull-request-available
• Lucene Fields: New
• Assignee: Unassigned
• Reporter: Paul Sanwald
• Created: 23/Oct/19 00:31
• Updated: 28/Aug/22 15:52
• Resolved: 29/Oct/19 08:33

Description

There is a TODO in IntroSelector.java to use the median of medians algorithm instead of HeapSort for the worst case, as median of medians offers a better time complexity.

I've discussed this with jpountz and he has agreed to review my work on this.

Issue Links

• links to: GitHub Pull Request #966