The Spliterators returned by sorted collections such as ImmutableSortedSet and RegularImmutableAsList result in unnecessary sorting occurring when a sort operation is performed on their associated Stream. The root cause is that the
Spliterators' getComparator() implementations always return a Comparator instance, even when natural ordering is used.

According to the Javadoc, null should be returned by getComparator() to indicate the source items are sorted in natural order.

You can see here that the SORTED flag gets unset when a spliterator has the SORTED characteristic but does not return a null comparator. And here is where the missed optimization happens due to that.

The issue is trivially reproducible by doing the following, and stepping through the code in SortedOps where the expected no-op / optimization would ideally happen:

ImmutableSortedSet<Integer> sortedSet = ImmutableSortedSet.of(1, 2, 3, 4);
// sorted should be a no-op, but isn't because ImmutableSortedSet's Spliterator does not return a null comparator.
sortedSet.stream().sorted().collect(Collectors.toList());