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

 

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

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

 

Задача 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 – Демонстрация выполнения алгоритма сортировки слиянием