[GitHub] [lucene-solr] jpountz commented on a change in pull request #966: LUCENE-9024 Optimize IntroSelector to use median of medians

[GitBox <gi...@apache.org>]

jpountz commented on a change in pull request #966: LUCENE-9024 Optimize IntroSelector to use median of medians
URL: https://github.com/apache/lucene-solr/pull/966#discussion_r338913879
 
 

 ##########
 File path: lucene/core/src/java/org/apache/lucene/util/IntroSelector.java
 ##########
 @@ -33,26 +32,87 @@ public final void select(int from, int to, int k) {
     quickSelect(from, to, k, maxDepth);
   }
 
-  // heap sort
-  // TODO: use median of median instead to have linear worst-case rather than
-  // n*log(n)
-  void slowSelect(int from, int to, int k) {
-    new Sorter() {
+  int slowSelect(int from, int to, int k) {
+    return medianOfMediansSelect(from, to-1, k);
+  }
+
+  int medianOfMediansSelect(int from, int to, int k) {
 
 Review comment:
   It took me a while to figure out that `to` is inclusive here while it is exclusive elsewhere in this file (e.g. in `select` and `quickselecet`). Maybe rename it to `toInclusive` or something along those lines to make it clear? Or maybe call them `left` and `right` like you did in some other methods?

----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
 
For queries about this service, please contact Infrastructure at:
users@infra.apache.org


With regards,
Apache Git Services

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org