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

Вступление

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

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

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

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

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

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

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

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

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

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

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

Реализация

Чтобы упростить алгоритм, мы будем использовать два метода – Сортировка слиянием () , который разделит коллекцию и рекурсивно вызовет себя, и его вспомогательный метод, 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);
}

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

В противном случае мы разделяем массив на две половины и вызываем 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));

Git Essentials

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

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

Первый запуск	0.00551
Второй заход	0.00852
Третий заход	0.00765
Четвертый прогон	0.00543
Пятый прогон	0.00886
Шестой прогон	0.00946
Седьмой прогон	0.00575
Восемь Пробегов	0.00765
Девятый прогон	0.00677
Десятый прогон	0.00550

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

Вывод

Еще следует отметить, что сортировка слиянием-это “неуместный” алгоритм сортировки. Это означает, что ему требуется дополнительное пространство для хранения элементов его сортировки, что может вызвать проблемы в системах с ограниченным объемом памяти. Это один из компромиссов в использовании этого алгоритма.

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