On Sat, 3 Oct 2026 21:13:05 GMT, Vladimir Yaroslavskiy <[email protected]> wrote:
> 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). Original / duplicated bugs https://bugs.openjdk.org/browse/JDK-8080966 https://bugs.openjdk.org/browse/JDK-8076446 ------------- PR Comment: https://git.openjdk.org/jdk/pull/33190#issuecomment-5973702674
