В стандартной библиотеке Java существует ли метод, позволяющий сортировать ArrayList на месте, т.е. используя O(1) дополнительное хранилище?
Collections.sort(List<T>) не выполняет это требование, так как он
удаляет указанный список в массив, сортирует массив и выполняет итерацию по списку, сбросив каждый элемент из соответствующей позиции в массиве.
Если в стандартной библиотеке нет ничего, какие сторонние библиотеки могут быть использованы для этого?
Вы можете извлечь базовый массив (например, отражение) и выполнить на нем массив Arrays.sort(массив, 0, list.size()).
Java 7 не копирует массив в Arrays.sort() перед сортировкой массива. В Java 6 это означает, что Collections.sort() в Java 6 фактически копирует базовый массив TWICE для выполнения сортировки.
Collections.sort() был создан для работы с любой реализацией List и почему он не работает на месте (слияние LinkedList на месте сложно и жертвует стабильностью).
Если вы действительно обеспокоены сортировкой на месте, вам придется развернуть свою собственную функцию сортировки. Это не стоит вашего времени, если ваш список очень длинный.
Arrays.sort(Object[]) выполняет одно и то же объединение и вызывается внутри Collections.sort() (по крайней мере, в openjdk)
Просто, нет. Collections.sort() был создан для сортировки, кажется, что вы должны реализовать свои собственные. Для списков я бы использовал Bubblesort, потому что он просто обменивает два соседних элемента, что можно сделать очень просто без изменения ковшей.