sorting - Big-O complexity of java.util.stream.Stream<T>.sorted()

Question

Does anyone know what the time complexity of java.util.stream.Stream<T>.sorted() is?

Answer 1

Well, sorted() in itself is O(1), since it's an intermediate operation that doesn't consume the stream, but simply adds an operation to the pipeline.

Once the stream is consumed by a terminal operation, the sort happens and either

• it doesn't do anything (O(1)) because the stream knows that the elements are already sorted (because they come from a SortedSet, for example)
• or the stream is not parallel, and it delegates to Arrays.sort() (O(n log n))
• or the stream is parallel, and it delegates to Arrays.parallelSort() (O(n log n))