jpountz commented on code in PR #12623:
URL: https://github.com/apache/lucene/pull/12623#discussion_r1346923517
##########
lucene/core/src/java/org/apache/lucene/util/StableMSBRadixSorter.java:
##########
@@ -78,4 +78,60 @@ protected void reorder(int from, int to, int[] startOffsets,
int[] endOffsets, i
}
restore(from, to);
}
+
+ /** A MergeSorter taking advantage of temporary storage. */
+ protected abstract class MergeSorter extends Sorter {
+ @Override
+ public void sort(int from, int to) {
+ checkRange(from, to);
+ mergeSort(from, to);
+ }
+
+ private void mergeSort(int from, int to) {
+ if (to - from < BINARY_SORT_THRESHOLD) {
+ binarySort(from, to);
+ } else {
+ final int mid = (from + to) >>> 1;
+ mergeSort(from, mid);
+ mergeSort(mid, to);
+ merge(from, to, mid);
+ }
+ }
+
+ /**
+ * We tried to expose this to implementations to get a bulk copy
optimization. But it did not
+ * bring a noticeable improvement in benchmark as {@code len} is usually
small.
+ */
+ private void bulkSave(int from, int tmpFrom, int len) {
+ for (int i = 0; i < len; i++) {
+ save(from + i, tmpFrom + i);
+ }
+ }
+
+ private void merge(int from, int to, int mid) {
+ assert to > mid && mid > from;
Review Comment:
In merge sort, it is common to check if the value at mid-1 is less than or
equal to the value at mid, to save work in case the data is already (partially)
sorted, maybe we could do that here too?
--
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.
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
