Почему реализация Arrays.sort от Sun создает клон входного массива?

Question

Может кто-нибудь объяснить, пожалуйста, следующий код?

Источник: Arrays.class,

public static <T> void sort(T[] a, Comparator<? super T> c) {
T[] aux = (T[])a.clone();
    if (c==null)
        mergeSort(aux, a, 0, a.length, 0);
    else
        mergeSort(aux, a, 0, a.length, 0, c);
}

1. Зачем создавать aux?
2. Как работает сортировка, если код сортирует aux?
3. Разве это не пустая трата ресурсов на клонирование массива перед сортировкой?

Answer 1

1: Зачем создавать aux?

Поскольку метод mergeSort требует массива источника и назначения.

2: Как происходит сортировка?работает, если код сортирует aux?

Поскольку метод mergeSort сортирует от aux до a

3: Разве это не пустая трата ресурсов на клонирование массива перед сортировкой?

Нет, это не ... использование этой реализации mergeSort.Теперь, если sort вернул отсортированный массив, создание клона (а не создание пустого массива) было бы расточительным.Но API требует, чтобы он выполнял сортировку на месте, а это означает, что a должно быть «местом назначения».Поэтому элементы необходимо скопировать во временный массив, который будет «источником».

Если вы посмотрите на метод mergeSort, вы увидите, что он рекурсивно разбивает массив для сортировки, объединяявперед и назад между массивами источника и назначения.Чтобы это работало, вам нужно два массива.Предположительно Sun / Oracle определили, что этот алгоритм обеспечивает хорошую производительность для типичных сценариев использования Java-сортировки.

Answer 2

Чтение mergeSort источника .

Это не-место сортировки с двумя параметрами (src и dest).
Сортировка destпараметр и использует параметр src для справки.

Answer 3

Прокрутите вниз в этом исходном файле и посмотрите, как работает рекурсивная сортировка mergeSort. Я думаю, что это слишком сложно, чтобы попытаться объяснить в посте здесь, так что вот хорошая ссылка:

http://en.wikipedia.org/wiki/Merge_sort