Краткий ответ

sorted — это состоящая из состояния промежуточная операция: чтобы выдать первый элемент в правильном глобальном порядке, ей обычно нужно накопить и сравнить весь входной набор. В параллельном режиме части данных сортируются отдельно, затем объединяются, поэтому возникают барьер синхронизации, дополнительные буферы и стоимость слияния.

Исторический контекст

Stream API появился в Java 8 как декларативный способ описывать обработку последовательностей и потенциально выполнять независимые этапы параллельно. Для простых поэлементных операций достаточно передавать элементы по конвейеру, но такие задачи, как сортировка, требуют информации сразу о множестве элементов.

Поэтому в API есть различие между stateless-операциями, которым не нужно помнить предыдущие элементы, и stateful-операциями, которые накапливают состояние. sorted относится ко второй группе и сохраняет удобную декларативную модель, принимая на себя стоимость глобального упорядочивания.

Постановка проблемы

До сортировки параллельный стрим может обрабатывать разные части источника независимо. Однако первый элемент результата нельзя корректно выдать только на основании одной части: меньший элемент может находиться в любой другой части.

Если неверно оценить это свойство, параллельную сортировку применяют к большим данным, ожидая почти линейного ускорения. На практике растут объём временной памяти, задержка до появления первых результатов и затраты на синхронизацию; на небольших наборах последовательная обработка нередко оказывается быстрее.

Подробное решение

В последовательном конвейере sorted накапливает элементы, сортирует их по естественному порядку или переданному Comparator, а затем передаёт downstream-операциям. Это нарушает обычную потоковую обработку: элементы после сортировки не обязаны появляться сразу после поступления во вход.

В параллельном конвейере источник разделяется на части. Каждая часть может быть обработана и отсортирована отдельно, после чего реализации необходимо построить глобально отсортированный результат, обычно через объединение отсортированных сегментов или эквивалентный этап. Граница между накоплением и выдачей результата является глобальным барьером.

Минимальная иллюстрация проблемы:

List<Integer> result = numbers.parallelStream()
    .sorted()
    .limit(100)
    .toList();

limit после sorted не отменяет необходимость рассмотреть вход для сортировки: первые 100 элементов становятся известны только после определения глобального порядка. Если нужен лишь небольшой top-K, часто лучше применить специализированный алгоритм с ограниченной очередью или выполнить сортировку в базе данных, где доступны индексы и оптимизатор.

Параллельность может помочь, когда данных много, сравнение элементов дорогое, источник хорошо разбивается, а памяти достаточно. Она менее привлекательна при маленьком объёме, дешёвом сравнении, плохом разбиении источника или высокой конкуренции за память.

Ситуация из практики

Сервис анализирует десятки миллионов событий и должен вернуть 100 событий с минимальным временем обработки. Вариант с parallelStream().sorted().limit(100) прост, но сортирует весь набор, создаёт значительный объём промежуточных данных и задерживает выдачу результата.

Полная последовательная сортировка предсказуема и может быть достаточно быстрой на умеренном объёме, но имеет асимптотику порядка O(n log n) и также требует хранения данных. Параллельная сортировка сокращает время вычислений только при подходящей нагрузке, но добавляет расходы на разделение, слияние и память.

Выбранное решение — поддерживать ограниченную структуру top-K размером 100 и объединять такие структуры между рабочими частями, либо перенести выборку на уровень базы данных при наличии подходящего индекса. Это уменьшает память примерно до O(k) для одного результата и избегает полной сортировки, сохраняя точный результат; цена решения — более сложный код или зависимость от возможностей хранилища.

Что кандидаты часто упускают

Можно ли считать sorted ленивой операцией?

Да, вызов операции ленив в том смысле, что сортировка не начинается до терминальной операции. Но после запуска конвейера сама сортировка остаётся накопительной: ленивость вызова не означает, что результат будет выдаваться по одному элементу без ожидания полного входа.

Почему sorted().limit(k) обычно не равноценно выбору минимальных k элементов?

Полная сортировка упорядочивает весь набор, а затем отбрасывает всё после позиции k. Для задачи top-K достаточно поддерживать только k лучших элементов, поэтому специальный алгоритм может снизить затраты с полной сортировки до порядка O(n log k) и существенно уменьшить память. Это корректно только при явно определённом порядке и корректном сравнении элементов.

Сохраняет ли sorted порядок равных элементов в параллельном стриме?

Для упорядоченного стрима сортировка является стабильной: элементы, эквивалентные по компаратору, сохраняют их encounter order. Для неупорядоченного стрима порядок эквивалентных элементов не гарантируется, поэтому полагаться на их взаимное расположение нельзя, даже если итоговые ключи отсортированы.