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

Сортировка слиянием (англ. merge sort) является простым, но эффективным алгоритмом сортировки, который также как и алгоритм быстрой сортировки построен по принципу «разделяй и властвуй», однако реализует его несколько по-другому. Массив делится пополам, левая и правая половина рекурсивно сортируется тем же методом слияния, затем отсортированные части объединяются в один отсортированный массив. В соответствии с алгоритмом деление продолжается до части массива, состоящего из одного элемента. Такой массив сразу является отсортированным, поэтому задача сводится к написанию метода, который выполняет слияния двух отсортированных частей массива в один.

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

Задача 6.7 Напишите рекурсивный метод сортировки слиянием целочисленного массива.

Объяснение: в программе используются следующие методы:

mergeSort (int[] arr) — выполняет сортировку массива arr[], вызывая для этого методmergeSort (int[] arr, int low, int high, int[] buff);

mergeSort (int[] arr, int low, int high, int[] buff) — выполняет сортировку массива arr[] от индекса low до индекса high. В качестве аргумента в метод передается вспомогательный буфер buff[]. Метод осуществляет рекурсивное деление массива пополам и вызов метода слияния merge ().

merge (int[]arr, int low, int high, int mid, int[] buff) — метод выполняет слияние отсортированных частей массива: левой от идекса low до mid и правой от индексаmid+1 до индекса high.

Пример выполнения алгоритма сортировки слиянием массива {5, 0, -10, 9, 15, 100, -12, 3} иллюстрирует рис. 6.5.

public class MergeSort {.

static void mergeSort (int[] arr) {.

mergeSort (arr, 0, arr. length — 1, new int[arr.length]);

}.

static void mergeSort (int[] arr, int low, int high, int[] buff){.

//Выполняем разделение.

if (low >= high) {.

return;

}.

int mid = (low + high)/2;

mergeSort (arr, low, mid, buff);

mergeSort (arr, mid+1, high, buff);

//Вызываем метод слияния.

merge (arr, low, high, mid, buff);

}.

static void merge (int[]arr, int low, int high, int mid, int[] buff).

{.

int left = low, right = mid + 1;

//Выполняем слияние.

for (int i = low; i <= high; i++) {.

if (right>high||left<=mid && arr[left]<=arr[right]).

{.

buff[i] = arr[left++];

} else {.

buff[i] = arr[right++];

}.

}.

//Копируем буфер в массив arr.

for (int i = low; i <= high; i++) {.

arr[i] = buff[i];

}.

}.

public static void main (String[]args) {.

int[] a = {5,0,-10,9,15,100,-12,3};

mergeSort (a);

System.out.println (java.util.Arrays.toString (a));

}}.

Результат:

[-12, -10, 0, 3, 5, 9, 15, 100].

Сортировка слияниемявляется одним из самых простых алгоритмов сортировки среди быстрых алгоритмов, который может быть эффективно использован для сортировки связанных списков. Недостаток алгоритмазаключается в том, что он требует дополнительную память размером порядкаn, и не гарантирует сохранение порядка элементов с одинаковыми значениями. Его временная сложность всегда пропорциональна.

Рис. 6.6 — Демонстрация выполнения алгоритма сортировки слиянием