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

[Piotr Findeisen]

Hi Paul,

I think this is also how it looks like in Java 8 (but I also checked docs &
code in 9 before posting).
Basically, in List.sort docs, the word "stable" is @implNote for *default
implementation*, not a contract that a subclass implementor must obey.
At least I understand this that way.

Thus, for List not having specialised sort implementation,
Collections.sort(List) will be stable sort.
For a List that has specialised sort implementation (that happens not to be
stable),  Collections.sort(List)  will not be stable as well, even though
javadoc expressly promises that.

Best regards,
Piotr




On Thu, Nov 16, 2017 at 5:54 PM, Paul Sandoz <paul.sandoz at oracle.com> wrote:

> 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
>
> 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
>
>
>