Java – How does sorting with java 8 stream work under the hood

javajava8stream-processing

When I call Stream.sort(..) is there a new array of elements created and the stream iterates over the newly created sorted array?

In other words, how Java 8 Stream does sort under the hood?

Best Answer

You can use grepcode.com to search through the Java standard library code (and some other libraries). Unfortunately, the stream implementation code is rather abstract. A good starting point is the internal java.util.stream.SortedOps class which transforms a stream into a sorted stream.

The current implementation (used for streams of standard library containers) makes it a no-op if the stream is already sorted, uses an array if the size of the stream is known (SizedRefSortingSink), or accumulates all elements in an ArrayList if the size is unknown (RefSortingSink).

Of course, such implementation details may change with any release, but the fundamental considerations are universal: Sorting a stream is necessarily an eager/blocking operation, and sorting an infinite stream is not meaningful. This means sorting a stream is not useful if you use streams because they can be lazy, but you still get the convenient stream syntax.

Other streams will have to provide their own implementation of Stream.sorted(), which will likely be similar.

Related Solutions

Java and .NET – Why Different Sorting Algorithms Are Used by Default

As deterministic as computers themselves are, computer engineering is not an exact science. Two people, given the same problem domain, will perform an analysis and develop two different solutions that satisfy all constraints of the problem. It may be difficult or impossible to empirically determine which of these is "better" in the general case.

My guess is that the .NET QuickSort is layered on top of something in the MFCs or Windows API, and is probably inherited from much older versions of Windows where the multi-threadable advantage of MergeSort wouldn't have even been considered for the computers of the day. (EDIT: it's not, though Microsoft developers have been QuickSort fanboys for a long time, as evidenced by this choice of sorting implementation since MS-DOS).

Java, which can't use any platform-specific implementation because Java was designed from scratch to be completely platform-independent, went a different way. Who knows why MergeSort came out on top; my wild guess is that the implementation won some sort of performance competition versus some other sorts the developers came up with, or else that an O(n)-space MergeSort just looked best on paper in terms of best-case and worst-case performance (MergeSort has no Achilles' heel relating to element selection like QuickSort, and its best-case is a near-sorted list while that's often QuickSort's worst). I doubt multithreading benefits were initially considered, but the current implementation may well be multithreaded.

Java – How to Transition from JavaScript to Java

Using arrays for everything is a bad idea. Even in JavaScript. But in Java even more so, because arrays are far more narrow in Java.

The elements of your return array are in fact representing results. You should communicate it accordingly:

class Result {
     public int someInt;//no idea what this actually is, but a class will allow you giving it a proper name
     public String someString;//same as with the other field. Also, I suppose String is actually wrong here, since it rather looks like a '-'-separated list of integers, which should rather be represented as an array of integers
     Result(String someString, int someInt) {
           this.someString = someString;
           this.someInt = someInt;
     }
}

And then your return value should look something like:

ArrayList.ofList(new Result('1-3-5', 50), new Result('2-5-8', 90), new Result('2-4-7', 75))

Best Answer

Related Solutions

Java and .NET – Why Different Sorting Algorithms Are Used by Default

Java – How to Transition from JavaScript to Java

Related Topic