Вступление
Сортировка - важный аспект обработки данных. Для нас, людей, гораздо естественнее сортировать вещи, которые имеют что-то общее, например, дату публикации, алфавитный порядок, статьи, принадлежащие автору, от наименьшего к наибольшему и т. Д. Это значительно упрощает понимание данных, поскольку они логически связаны, а не рассредоточены вокруг.
И что не менее важно, компьютерам легче работать с отсортированными массивами. Например, в отсортированном массиве можно искать намного быстрее, как с алгоритмом двоичного поиска , который выполняется за время O (logn) . Такой алгоритм просто не работает без отсортированного массива.
Сортировка слиянием
Сортировка слиянием - это алгоритм «разделяй и властвуй» , который рекурсивно вызывает себя на половинных частях исходной коллекции.
При этом это очень похоже на Quicksort , который также разделяет коллекцию, а затем рекурсивно вызывает себя для секционированных коллекций (которые обычно являются половинками).
Основное отличие заключается в том, что Quicksort - это внутренний алгоритм сортировки на месте , а Merge Sort - это внешний алгоритм сортировки вне места.
Обычно это делается с коллекциями, которые слишком велики для загрузки в память, и мы загружаем их по частям по мере необходимости. Таким образом, сортировке слиянием не нужно хранить всю коллекцию в памяти, из которой она может легко и произвольно обращаться к каждому элементу в любой момент времени. Скорее, коллекция может храниться во внешнем месте, например на диске (или гораздо раньше - на ленте), с которого загружаются необходимые элементы.
При этом сортировка слиянием должна заниматься оптимизацией такой загрузки и выгрузки, поскольку она может работать довольно медленно с большими коллекциями.
Как упоминалось выше, сортировка слиянием - это неуместный алгоритм сортировки. Это означает, что сортировка слиянием не сортирует и не сохраняет элементы в адресах памяти данной ей коллекции, а вместо этого создает и возвращает полностью новую коллекцию, которая является отсортированной версией предоставленной ей.
Это важное различие из-за использования памяти. Для очень больших массивов это будет недостатком, поскольку данные будут дублироваться, что может вызвать проблемы с памятью в некоторых системах.
Вот визуальное представление того, как это работает:
{.ezlazyload}
Выполнение
Чтобы усовершенствовать алгоритм, мы будем использовать два метода -
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) , что справедливо для алгоритма сортировки. Вот как это работает после сортировки массива, содержащего 10000 целых чисел в случайном порядке:
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,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