Ответ
Используйте ArrayList для хранения, т.к. он обеспечивает быстрый доступ и эффективное заполнение. Для сортировки примените Collections.sort() или List.sort(), которые используют TimSort (гибридный алгоритм с O(n log n)).
Оптимизации:
- Предварительный размер:
List<Item> list = new ArrayList<>(1_000_000_000); // избегаем реаллокаций
- Примитивы: Если возможно, используйте
TroveилиEclipse Collectionsдля примитивов. - Параллельная сортировка:
list.parallelStream().sorted().collect(Collectors.toList());
- Офф-хип: Для уменьшения нагрузки на GC храните данные в
byte[]илиMemoryMappedFile.
Для очень больших данных рассмотрите внешнюю сортировку (разбивка на чанки + слияние).