The 30 second answer
It is a stateful barrier: it buffers every upstream element, sorts them when the upstream ends, then pushes downstream. For ordered streams the sort is stable. Natural-order sorted needs Comparable elements. Putting sorted on an infinite stream never finishes, and limit after sorted does not save you.
[Docs] Stateful; stable for ordered streams. No-arg sorted() requires Comparable elements or throws ClassCastException at terminal time.
[Impl] From OpenJDK SortedOps (jdk-21+35): it is a barrier — it buffers all upstream elements (into an array when size is known, otherwise an ArrayList / spined buffer), sorts at end() using Arrays.sort / List.sort (TimSort for objects, stable), then pushes downstream. If the upstream is already SORTED with natural order, the op is skipped. In parallel it sorts via Arrays.parallelSort.
Consequence: O(n log n) time, O(n) memory, and sorted() on an infinite stream never completes (limit after sorted does not help).
Sources: