ADDITIONAL SYSTEM INFORMATION :
All versions of JDK since 8 are affected.

A DESCRIPTION OF THE PROBLEM :
If a Collection such as a SortedSet or SortedMap uses the explicit natural ordering via Comparator.naturalOrder(), it disables optimizations for any associated streams to skip the sorting step if requested. This is because StreamOpFlag.fromCharacteristic removes the SORTED flag for the Stream if the comparator is not null. The result is that extra copying and an unnecessary sorting operation can occur if sorted() is called on the associated stream.

To reproduce, run the following:

TreeSet<Integer> sortedSet = new TreeSet<>(Comparator.naturalOrder());
sortedSet.add(1);
sortedSet.add(2);
Object[] ignored = sortedSet.stream().sorted().toArray();

And with a debugger observe that internally SizedRefSortingSink is used, which allocates a new array and performs an sort.