Which algorithm use sorted method in Stream interface [closed]

Question

When I print the values in the sorted method,

Stream.of("d", "a", "b", "e", "c", "f")
    .sorted((s1, s2) -> {
        System.out.printf("sort: %s - %s\n", s1, s2);
        return s1.compareTo(s2);
    }).forEach(System.out::println);

The output is as follows;

sort: a - d
sort: b - a
sort: b - d
sort: b - a
sort: e - b
sort: e - d
sort: c - d
sort: c - b
sort: f - c
sort: f - e
a
b
c
d
e
f

I could not understand the logic of the sorting algorithm here. Any help will be appreciated.

Answer 1

The answer below is relevant to OpenJDK (checked against 10.0.1).

Streams delegate the sorting operations to the relevant Arrays.sort methods (see end methods of various SortingOps).

Sorting streams of objects

For sorting objects, TimSort (basically a merge sort which uses insertion sort when the divisions of the input are small enough) is the preferred method.

The authors credit Tim Peter's implementation of list sort in Python as an inspiration, further attributing the idea to the paper "Optimistic Sorting and Information Theoretic Complexity", Peter McIlroy, SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms), 467-474, Austin, Texas, 25-27 January 1993.

However the user can also request MergeSort (falling back to insertion sort when the arrays are small enough - in OpenJDK 10 it's 32 or fewer elements) to be used by setting the java.util.Arrays.useLegacyMergeSort property to true. This is planned to be removed in future releases.

Sorting streams of primitives

For sorting streams of primitives (byte, char, short, int, long, float, double) - dual pivot quicksort is implemented. The authors (Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch) do not give any more information about where the inspiration came from.

Sources

To learn more, see OpenJDK code:

• SortedOps.java - implementation relevant to the streams

• Arrays.java - implementation of the Arrays helper, see the different sort methods

• TimSort.java - implementation of TimSort

• ComparableTimSort.java - variation for classes implementing Comparable

• DualPivotQuicksort.java - implementation of sorting for primitives