Why sorted operation impose an encounter order to a Stream?

Question

The documentation of the sorted operation says :

For ordered streams, the sort is stable. For unordered streams, no stability guarantees are made.

Some intermediate operations, such as sorted(), may impose an encounter order

Can someone explain why sorted operation needs an encounter order to the Stream (I don't see the relationship between the presence of an encounter order and the sorting operation) ?

Does that mean the following code is not valid (as HashSet is not intrinsically ordered) ?

Set<Integer> mySet = new HashSet<>();
mySet.add(10);
mySet.add(4);
mySet.add(20);
mySet.add(15);
mySet.add(22);
mySet.add(-3);

List<Integer> result = mySet.stream().sorted().collect(Collectors.toList());

System.out.println(result);

When I run this code, it always give me the same output [-3, 4, 10, 15, 20, 22]

Event if I use .parrallel(), the output remains the same [-3, 4, 10, 15, 20, 22]

mySet.stream().parallel().sorted().collect(Collectors.toList());`

The issue is that if the sort is unstable, equal items may not be in the same position they started in. This is important if there are other attributes in the items that are being sorted. In your example it is irrelevant since there is only a single value, an integer. [This](https://stackoverflow.com/questions/45085055/encounter-order-preservation-in-java-stream) may also help. — WJS, Dec 03 '19 at 19:57
it should have be written in the documentation because it's not very clear. This post https://stackoverflow.com/questions/41894173/java-8-findfirst-and-encounter-order/41895946#41895946 shows a concrete example on how disinct is affected by the order — Olivier Boissé, Dec 03 '19 at 20:16
Note that `parallel()` does not demand parallel operation. It is only a suggestion. And for that small amount of items, Java will most likely not follow your suggestion. — Zabuzard, Dec 03 '19 at 20:21
That’s the whole point in sorting in a stream: establishing a (partial) encounter order. — Ole V.V., Dec 03 '19 at 20:26
@OlivierBoissé It *is* written in the documentation. That's what stable sorting means. — user207421, Dec 03 '19 at 21:37
@user207421 Yes I misunderstood the word stable, that's clear now ! — Olivier Boissé, Dec 04 '19 at 07:34
Above, I said "same position." Same "relative order" would have been a better choice of words. — WJS, Dec 06 '19 at 16:37

score 13 · Accepted Answer · answered Dec 03 '19 at 20:40

When I run this code, it always give me the same output

Yes. It sorts the set, as expected. It seems you have misinterpreted the word 'stable'. Stability in a sort refers to not moving equal elements.

Stable sort algorithms sort repeated elements in the same order that they appear in the input

Why sorted operation impose an encounter order to a Stream?

1 Answers1