I'm improving the quality of sorting tests as a part of PR
https://github.com/openjdk/jdk/pull/27411 and found a bug in parallel sorting.
According to the javadoc object sorting Arrays.sort() and Arrays.parallelSort()
are _stable_ (keep the order of the elements with the same key), but a simple
test shows that parallel sort of objects doesn't work correctly, see the test:
import java.util.Arrays;
import java.util.Comparator;
public class ParallelStabilityTest {
private static final int LENGTH = 16_385;
public static void main(String[] args) {
Pair[] a = new Pair[LENGTH];
for (int i = 0; i < LENGTH; ++i) {
a[i] = new Pair(1, i);
}
Arrays.parallelSort(a); // failed
// Arrays.parallelSort(a, byKey); // failed
// Arrays.sort(a); // ok
// Arrays.sort(a, byKey); // ok
checkStability(a);
System.out.println("PASSED");
}
record Pair(int key, int index) implements Comparable<Pair> {
@Override
public int compareTo(Pair p) {
return Integer.compare(key , p.key);
}
@Override
public String toString() {
return "[" + key + ", " + index + "]";
}
}
private static final Comparator<Pair> byKey =
Comparator.comparingInt(Pair::key);
private static void checkStability(Pair[] a) {
for (int i = 1; i < a.length; ++i) {
if (a[i - 1].key == a[i].key && a[i - 1].index > a[i].index) {
System.out.println("FAILED: not stable at i = " + i + ": " +
a[i - 1] + " and " + a[i]);
System.exit(1);
}
}
}
}
The root of the problem actually is not in parallelism, but in the algorithm of
part merging. We split larger and find point in smaller in method
Merger.compute() from class ArraysParallelSortHelpers, but if we have parts of
equal elements, it doesn't work correctly, comparison in `else` branch must be
strong (`<`). The fix is very simple: `<=` -> `<`.
---------
- [x] I confirm that I make this contribution in accordance with the [OpenJDK
Interim AI Policy](https://openjdk.org/legal/ai).
-------------
Commit messages:
- JDK-8393047: Arrays.parallelSort sorting of objects is not stable: updated
year: 2026
- JDK-8393047: Arrays.parallelSort sorting of objects is not stable
Changes: https://git.openjdk.org/jdk/pull/33190/files
Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=33190&range=00
Issue: https://bugs.openjdk.org/browse/JDK-8393047
Stats: 62 lines in 2 files changed: 38 ins; 6 del; 18 mod
Patch: https://git.openjdk.org/jdk/pull/33190.diff
Fetch: git fetch https://git.openjdk.org/jdk.git pull/33190/head:pull/33190
PR: https://git.openjdk.org/jdk/pull/33190
