Идея алгоритма сортировки слиянием:
Разделяй — властвуй; каждый рекурсивный процесс включает в себя три этапа. Во-первых, декомпозиция: разложить последовательность из n элементов, подлежащих сортировке, на две подпоследовательности, каждая из которых включает n/2 элементов.
Во-вторых, управление: вызовите MergeSort для каждой подпоследовательности отдельно и выполните рекурсивные операции. В-третьих, слияние: объедините две отсортированные подпоследовательности для генерации результатов сортировки.
public static void mergeSort(int[] a, int[] tmp, int left, int right) { if (left < right) { int middle = left + (right - left) / 2; mergeSort(a, tmp, left, middle);// Сортировка слева mergeSort(a, tmp, middle + 1, right);// Сортировка справа merge(a, tmp, left, middle + 1, right);// Объединить левое и правое} } public static void merge(int[] a, int[] tmp, int left, int rightPos, int right) { int leftEnd = rightPos - 1; int tmpPos = left; 1; while (left <= leftEnd && rightPos <= right) { if (a[left] < a[rightPos]) { tmp[tmpPos++] = a[left++] } else { tmp[tmpPos++] = a[rightPos++]; } } while (left <= leftEnd) { tmp[tmpPos++] = a[left++] } while (rightPos <= right) { tmp[tmpPos++]; ] = a[rightPos++] } for (int i = 0; i < num; i++, right--) { a[right] = tmp [справа]; } }Принципиальная схема алгоритма слияния:
Выше приведено все содержание этой статьи, надеюсь, она вам всем понравится.