Is Collections.sort(List) still stable (java 8, 9..)?
paul.sandoz at oracle.com
Thu Nov 16 16:54:34 UTC 2017
In Java 9 we moved some documentation from Collectors.sort(List ) to List.sort, then back ported it. For more details see https://bugs.openjdk.java.net/browse/JDK-8030848 <https://bugs.openjdk.java.net/browse/JDK-8030848>
* This implementation is a stable, adaptive, iterative mergesort that
* requires far fewer than n lg(n) comparisons when the input array is
* partially sorted, while offering the performance of a traditional
* mergesort when the input array is randomly ordered. If the input array
* is nearly sorted, the implementation requires approximately n
* comparisons. Temporary storage requirements vary from a small constant
* for nearly sorted input arrays to n/2 object references for randomly
* ordered input arrays.
Overall specification has not changed with regards to stable sorting.
> On 16 Nov 2017, at 04:49, Piotr Findeisen <piotr.findeisen at gmail.com> wrote:
> I just realised the Collections.sort(List) method ceased to be stable as of
> Java 8 (sort of).
Do you have a specific bug or are you unsure with regards to the specification?
> Although the method's documentation still promises stable sort, the
> implementation delegates to List.sort(Comparator) and that interface method
> bears no constraint that an implementation must sort stable.
> Is "stable" missing from List.sort's documentation?
> Or, instead, should it be now no longer promised by Collections.sort? (oh,
> Or, what am i missing?
> Best regards,
More information about the core-libs-dev