Definition
- Stateful: must see ALL elements before producing output. Buffers entire stream internally.
- O(n) memory: allocates an internal array to hold all elements for sorting.
- Blocks fusion: upstream elements are fully consumed into the buffer, then sorted, then emitted to downstream.
- Infinite streams: hangs forever or OOM because it cannot sort infinite data.
- Comparator:
sorted()uses natural order;sorted(Comparator)uses custom order. - Composition:
Comparator.comparing(fn).thenComparing(fn2).reversed()for multi-key sorting. - Parallel: requires merge-sort across partitions, adding overhead.
Stateless operations (filter, map) are assembly-line workers at National Bank of India: each cheque flows through one at a time. sorted() is the sorting machine that says 'give me ALL cheques first, then I will sort them and release them.' The machine holds ALL cheques (buffers) before outputting. If cheques keep coming forever (infinite stream), the machine never finishes.
Understanding the Concepts
What is sorted() and why is it stateful?
sorted() is a stateful intermediate operation that buffers ALL elements before emitting any. Unlike stateless filter and map which process one element at a time with O(1) memory, sorted must hold the entire stream contents in O(n) memory.
How do you sort with Comparator?
package com.bank.service;
import java.math.BigDecimal;
import java.util.*;
public class SortedDemo {
record Account(String id, String branch, BigDecimal balance) {}
public static void main(String[] args) {
List<Account> accounts = List.of(
new Account("SAV2001", "Mumbai", new BigDecimal("125000")),
new Account("CUR3001", "Delhi", new BigDecimal("250000")),
new Account("SAV2002", "Mumbai", new BigDecimal("50000")),
new Account("SAV2003", "Chennai", new BigDecimal("180000"))
);
// Single-key sort: balance descending
accounts.stream()
.sorted(Comparator.comparing(Account::balance).reversed())
.forEach(a -> System.out.println(a.id() + ": Rs." + a.balance()));
}
}
CUR3001: Rs.250000
SAV2003: Rs.180000
SAV2001: Rs.125000
SAV2002: Rs.50000
How do you sort with multiple keys?
// Multi-key sort: branch ascending, then balance descending
accounts.stream()
.sorted(Comparator.comparing(Account::branch)
.thenComparing(Account::balance, Comparator.reverseOrder()))
.forEach(a -> System.out.println(a.branch() + " " + a.id() + ": Rs." + a.balance()));
How does sorted() block fusion?
List.of("C", "A", "B").stream()
.peek(s -> System.out.println("before-sort: " + s)) // all 3 logged FIRST
.sorted()
.peek(s -> System.out.println("after-sort: " + s)) // then A, B, C
.toList();
before-sort: C
before-sort: A
before-sort: B
after-sort: A
after-sort: B
after-sort: C
All elements consumed before sorted emits anything.
Why is filter before sorted important?
// WRONG: sort ALL 100K, then filter to 10K
accounts.stream()
.sorted(Comparator.comparing(Account::balance)) // sorts 100K
.filter(a -> a.active()) // then keeps 10K
.toList();
// CORRECT: filter to 10K, then sort 10K
accounts.stream()
.filter(a -> a.active()) // reduces to 10K
.sorted(Comparator.comparing(Account::balance)) // sorts 10K (10x less!)
.toList();
What about null-safe sorting?
// nullsFirst: null values sort to the beginning
Comparator<Account> nullSafe = Comparator.comparing(
Account::branch, Comparator.nullsFirst(Comparator.naturalOrder()));
// nullsLast: null values sort to the end
Comparator<Account> nullSafeLast = Comparator.comparing(
Account::branch, Comparator.nullsLast(Comparator.naturalOrder()));
What happens with infinite streams?
// sorted on infinite stream: hangs forever or OOM!
// Stream.iterate(0, i -> i + 1).sorted().limit(10).toList(); // NEVER completes!
// CORRECT: limit BEFORE sorted
Stream.iterate(0, i -> i + 1).limit(10).sorted().toList(); // [0,1,2,3,4,5,6,7,8,9]
What is the stateful vs stateless comparison?
| Operation | State | Memory | Blocks fusion? |
|-----------|-------|--------|:-:|
| filter | Stateless | O(1) | No |
| map | Stateless | O(1) | No |
| sorted | Stateful | O(n) | Yes |
| distinct | Stateful | O(n) | Partial |
| limit | Stateful | O(1) | No |
| skip | Stateful | O(1) | No |
What should a senior engineer know?
- Always filter, limit, and distinct BEFORE sorted to minimise the buffer size.
- Never use sorted on infinite streams.
- In parallel streams, sorted requires merge-sort across partitions.
- For top-N queries,
sorted().limit(n)may use an optimised partial sort internally. - Comparator.comparing enables fluent sort composition with thenComparing for secondary keys and reversed() for descending order.
Visual Overview
sorted() blocks fusion:
────────────────────────
Source: [C, A, B]
│
peek: before-sort: C ← all consumed
peek: before-sort: A ← before sorted
peek: before-sort: B ← can emit
│
sorted: [A, B, C] ← buffers all, sorts
│
peek: after-sort: A ← now emits
peek: after-sort: B ← in sorted
peek: after-sort: C ← order
Stateful vs Stateless:
──────────────────────
filter, map → O(1) memory, one element at a time
sorted → O(n) memory, buffers everything
distinct → O(n) memory, HashSet of seen
limit, skip → O(1) memory, counter
Key Takeaway
sorted() is a stateful intermediate operation that buffers all elements in O(n) memory before sorting and emitting them. Unlike stateless filter and map which process one element at a time, sorted must see all elements. It blocks fusion and hangs on infinite streams.
The optimisation rule: filter before sorted to reduce the buffer size. Comparator.comparing enables fluent sort composition with thenComparing for secondary keys and reversed() for descending order.
Remember one sentence: sorted buffers everything in O(n) memory, so always filter first to sort fewer elements.
---