Сортировка слиянием в Java

И что не менее важно, с отсортированными массивами компьютерам легче работать. Например, отсортированный массив можно искать гораздо быстрее, как с помощью алгоритма двоичного поиска , который работает за время O(logn) . Подобный алгоритм просто не работает без отсортированного массива.

Сортировка слиянием

Сортировка слиянием — это алгоритм «разделяй и властвуй» , который рекурсивно вызывает себя для половинных частей исходной коллекции.

При этом это очень похоже на Quicksort , который также разбивает коллекцию на разделы, а затем рекурсивно вызывает себя для секционированных коллекций (которые обычно представляют собой половины).

Основное отличие заключается в том, что быстрая сортировка — это внутренний алгоритм сортировки на месте , а сортировка слиянием — внешний алгоритм сортировки не по месту.

Обычно это делается с коллекциями, которые слишком велики для загрузки в память, и мы загружаем их частями по мере необходимости. Таким образом, сортировке слиянием не требуется хранить всю коллекцию в памяти, из которой можно легко и произвольно получить доступ к каждому элементу в любой момент времени. Скорее, коллекция может храниться во внешнем месте, например на диске (а гораздо раньше — на ленте), с которого загружаются необходимые элементы.

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

Как упоминалось выше, сортировка слиянием — это алгоритм сортировки «не по месту» . Это означает, что сортировка слиянием не сортирует и не сохраняет элементы в адресах памяти предоставленной ей коллекции, а вместо этого создает и возвращает совершенно новую коллекцию, которая является отсортированной версией предоставленной ей.

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

Вот визуальное представление того, как это работает:

Выполнение

Чтобы упростить алгоритм, мы будем использовать два метода — mergeSort() который разделит коллекцию и рекурсивно вызовет сам себя, а также его вспомогательный метод, merge() который объединит результаты в правильном порядке.

Начнем с mergeSort():

public static void mergeSort(int[] array, int low, int high) {
    if (high <= low) return;

    int mid = (low+high)/2;
    mergeSort(array, low, mid);
    mergeSort(array, mid+1, high);
    merge(array, low, mid, high);
}

Эта часть довольно проста — мы предоставляем массив для сортировки, а low также high указатели на него. Если high указатель оказывается ниже или равен указателю low, мы просто return.

В противном случае мы разделяем массив на две половины и вызываем mergeSortот начала массива до середины, а затем вызываем его от середины до конца.

В конечном итоге мы вызываем merge() метод, который объединяет результаты в отсортированный массив:

public static void merge(int[] array, int low, int mid, int high) {
    // Creating temporary subarrays
    int leftArray[] = new int[mid - low + 1];
    int rightArray[] = new int[high - mid];

    // Copying our subarrays into temporaries
    for (int i = 0; i < leftArray.length; i++)
        leftArray[i] = array[low + i];
    for (int i = 0; i < rightArray.length; i++)
        rightArray[i] = array[mid + i + 1];

    // Iterators containing current index of temp subarrays
    int leftIndex = 0;
    int rightIndex = 0;

    // Copying from leftArray and rightArray back into array
    for (int i = low; i < high + 1; i++) {
        // If there are still uncopied elements in R and L, copy minimum of the two
        if (leftIndex < leftArray.length && rightIndex < rightArray.length) {
            if (leftArray[leftIndex] < rightArray[rightIndex]) {
               array[i] = leftArray[leftIndex];
               leftIndex++;
            } else {
                array[i] = rightArray[rightIndex];
                rightIndex++;
            }
        } else if (leftIndex < leftArray.length) {
            // If all elements have been copied from rightArray, copy rest of leftArray
            array[i] = leftArray[leftIndex];
            leftIndex++;
        } else if (rightIndex < rightArray.length) {
            // If all elements have been copied from leftArray, copy rest of rightArray
            array[i] = rightArray[rightIndex];
            rightIndex++;
        }
    }
}

Запуск следующего фрагмента кода:

int[] array = new int[]{5, 6, 7, 2, 4, 1, 7};
mergeSort(array, 0, array.length-1);
System.out.println(Arrays.toString(array));

Даст нам отсортированный массив:

[1, 2, 4, 5, 6, 7, 7]

Временная сложность

Средняя и наихудшая временная сложность сортировки слиянием равна O(nlogn) , что вполне справедливо для алгоритма сортировки. Вот как это произошло после сортировки массива, содержащего 10 000 целых чисел в случайном порядке:

int[] array = new int[10000];
for (int i = 0; i < array.length; i++) {
    array[i] = i;
}

// Shuffle array
Collections.shuffle(Arrays.asList(array));

// Print shuffled collection
for (int i = 0; i < array.length; i++) {
    System.out.println(array[i]);
}

long startTime = System.nanoTime();
mergeSort(array, 0, array.lenth-1);
long endTime = System.nanoTime();

// Print sorted collection
for (int i = 0; i < array.length; i++) {
    System.out.println(array[i]);
}

System.out.println();

// Print runtime in nanoseconds
System.out.println("Merge Sort runtime: " + (endTime - startTime));

А вот результаты через секунды после 10-кратного запуска:

При среднем времени выполнения 0,006 с это довольно быстро.

Заключение

Сортировка слиянием — это алгоритм «разделяй и властвуй» , который рекурсивно вызывает себя для половинных частей исходной коллекции.

Еще следует отметить, что сортировка слиянием — это алгоритм сортировки «неуместно» . Это означает, что для хранения элементов сортировки требуется дополнительное пространство, что может вызвать проблемы в системах с ограниченной памятью . Это один из компромиссов использования этого алгоритма.

Хотя это один из самых быстрых и эффективных алгоритмов сортировки со средней временной сложностью O(nlogn) , наряду с Quicksort, Timsort и Heapsort.