Как выполнить сортировку массивов с эффективным использованием памяти в Java?

Question

Я хочу отсортировать большой массив строк (в частности, File.list(), который я не могу экстернализировать или уменьшить) без использования [много] дополнительной памяти.

Arrays.sort() говорит, что выполняет сортировку слиянием, а википедия говорит, что некоторые реализации выделяют размер исходного массива для хранения отсортированного вывода. (Кажется, это подтверждается ссылкой System.arraycopy в методе).

Есть ли алгоритм сортировки на месте, который я могу использовать вместо этого, который эффективен для памяти?

Answer 1

Быстрая сортировка

на месте и очень быстрая. Смотрите здесь .

Answer 2

String является неизменным в Java. Таким образом, когда массив из String в вашем вопросе дублируется, они не требуют столько места, сколько вы ожидаете. На самом деле, накладные расходы могут быть весьма минимальными.

Другими словами, Java Arrays#sort() может быть просто идеальным для вашего решения. Вы можете проверить производительность самостоятельно.

Для вашего названия вопроса, ответ Ankit и ответ dlev вполне подойдут.

Answer 3

Вы можете написать алгоритм сортировки кучи для сортировки на месте.