Ad Infinitum Ad Infinitum - 3 months ago 18
Java Question

Which algorithm use sorted method in Stream interface

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.

Edit: The downvoters, please vote down with a reason, which helps me figure out what is wrong with the question.

Answer

After running it through debugger using OpenJDK 8, unsurprisingly, it turned out to be Timsort. It's basically a merge sort which uses insertion sort when the divisions of the input are small enough (32 or fewer elements with my version).

If you are interested in how it works in detail, refer to OpenJDK 8 Arrays::sort, for example on grepcode: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/Arrays.java?av=f

Comments