Is Collections.sort(List) still stable (java 8, 9..)?

[Paul Sandoz]

Hi Piotr,

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>

On List.sort:

* @implNote
* 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:
> 
> Hi,
> 
> 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?

Paul.

> 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,
> no!)
> Or, what am i missing?
> 
> Best regards,
> Piotr