Fixed a tiny bug in TimSort that slightly affects performance on small arrays
Martin Buchholz discovered this bug by running all tests with assertions
enabled. That's the only way he could have discovered it, as it doesn't
affect correctness:) The assertion that failed was the one at the head of
countRunAndMakeAscending. The cause was that I called the method with
(a, start, length) instead of (a, start, end).
diff --git a/libcore/luni/src/main/java/java/util/ComparableTimSort.java b/libcore/luni/src/main/java/java/util/ComparableTimSort.java
index 882add1..cda4b12 100644
--- a/libcore/luni/src/main/java/java/util/ComparableTimSort.java
+++ b/libcore/luni/src/main/java/java/util/ComparableTimSort.java
@@ -150,7 +150,7 @@
// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
- int initRunLen = countRunAndMakeAscending(a, lo, nRemaining);
+ int initRunLen = countRunAndMakeAscending(a, lo, hi);
binarySort(a, lo, hi, lo + initRunLen);
return;
}
diff --git a/libcore/luni/src/main/java/java/util/TimSort.java b/libcore/luni/src/main/java/java/util/TimSort.java
index 9c27ddc..4a9c05b 100644
--- a/libcore/luni/src/main/java/java/util/TimSort.java
+++ b/libcore/luni/src/main/java/java/util/TimSort.java
@@ -182,7 +182,7 @@
// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
- int initRunLen = countRunAndMakeAscending(a, lo, nRemaining, c);
+ int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
binarySort(a, lo, hi, lo + initRunLen, c);
return;
}
