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

Сортировка слиянием (англ. Merge sort, или mergesort) — эффективный алгоритм сортировки, основанный на операции слияния.

Сортировка слиянием — очень типичный пример применения подхода «разделяй и властвуй» (Divide and Conquer). Она объединяет уже упорядоченные подпоследовательности, чтобы получить полностью упорядоченную последовательность; то есть сначала упорядочивает каждую подпоследовательность, а затем упорядочивает отрезки между подпоследовательностями. Объединение двух упорядоченных списков в один упорядоченный список называется двусторонним слиянием.

Представьте, что вам нужно отсортировать полностью перетасованную колоду игральных карт. Эффективный способ таков: сначала разделите колоду на две меньшие стопки, отсортируйте каждую стопку отдельно, а затем объедините эти две упорядоченные стопки в одну полностью упорядоченную колоду.Сортировка слияниемИменно на этойконцепции «разделяй и властвуй»основан классический алгоритм сортировки.

Его основные операции можно свести к двум шагам:

  • Разделение: Рекурсивно разбивайте большой неупорядоченный список пополам снова и снова, разбивая его на множество небольших подсписков, пока каждый подсписок не будет содержать только один элемент (список из одного элемента, естественно, упорядочен).
  • Властвуй: Рекурсивно объединяйте эти упорядоченные подсписки попарно, сортируя в процессе объединения, и в конечном итоге объедините их в один полный упорядоченный список.

Применимость

Сортировка слиянием подходит для сценариев с большими объёмами данных и там, где требуется стабильность.

Сортировка слиянием — это стабильный алгоритм сортировки (то есть относительный порядок равных элементов после сортировки остаётся неизменным). Его временная сложность во всех случаях равна O(n log n), что делает его очень эффективным при обработке крупномасштабных данных, но его пространственная сложность равна O(n), потому что процесс слияния требует дополнительных массивов для временного хранения данных.

Следующая блок-схема наглядно показывает весь процесс «разделяй и властвуй» в сортировке слиянием:

Схема процесса

Сортировка слиянием — это пример рекурсивного алгоритма. Основная операция в этом алгоритме — слияние двух отсортированных массивов: на вход подаются два массива A и B, выходной массив C и три счётчика i, j, k, которые изначально установлены на начала соответствующих массивов.

Меньший из A[i] и B[j] копируется в следующую позицию в C, а соответствующий счётчик сдвигается на один шаг.

Когда один из двух входных массивов исчерпан, скопируйте оставшуюся часть другого массива в C.

Сортировка слиянием сверху вниз, схема рекурсивной группировки:

Выполните сортировку слиянием для данных в третьей строке, сгруппированных попарно.

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

Общая сортировка слиянием

Пример кода на Java

Загрузка пакета исходного кода:Скачать

Код файла MergeSort.java:

public class MergeSort {

    // Объединить две части arr[l...mid] и arr[mid+1...r]
    private static void merge(Comparable[] arr, int l, int mid, int r) {

        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);

        // Инициализация: i указывает на начальный индекс l левой половины; j указывает на начальный индекс mid+1 правой половины
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {

            if (i > mid) {  // Если все элементы в левой половине обработаны
                arr[k] = aux[j - l];
                j++;
            } else if (j > r) {   // Если все элементы в правой половине обработаны
                arr[k] = aux[i - l];
                i++;
            } else if (aux[i - l].compareTo(aux[j - l]) < 0) {  // Элемент, на который указывает индекс в левой половине, < элемента, на который указывает индекс в правой половине
                arr[k] = aux[i - l];
                i++;
            } else {  // Элемент, на который указывает индекс в левой половине, >= элемента, на который указывает индекс в правой половине
                arr[k] = aux[j - l];
                j++;
            }
        }
    }

    // Рекурсивно использовать сортировку слиянием для сортировки диапазона arr[l...r]
    private static void sort(Comparable[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        // Для случая, когда arr[mid] <= arr[mid+1], пропустить слияние
        // Это очень эффективно для почти упорядоченных массивов, но в общих случаях есть определённая потеря производительности
        if (arr[mid].compareTo(arr[mid + 1]) > 0)
            merge(arr, l, mid, r);
    }

    public static void sort(Comparable[] arr) {

        int n = arr.length;
        sort(arr, 0, n - 1);
    }

    // Тест MergeSort
    public static void main(String[] args) {

        int N = 1000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        sort(arr);
        // Вывести массив
        SortTestHelper.printArray(arr);
    }
}

Принципы алгоритма и подробные шаги

Реализация сортировки слиянием в основном опирается на две ключевые функции:merge_sort(отвечающая за «разделение») иmerge(отвечает за "управление").

1. Функция декомпозицииmerge_sort

Эта функция работает рекурсивно:

Базовый случай: если длина текущего массива меньше или равна 1, то он уже упорядочен, возвращаемся напрямую.

Рекурсивный случай：

  • Найти среднюю позицию массиваmid。
  • Для левой половиныarr[:mid]Рекурсивный вызовmerge_sort。
  • Для правой половиныarr[mid:]Рекурсивный вызовmerge_sort。
  • Наконец, вызватьmergeФункция объединяет уже отсортированные левую и правую части.

2. Функция слиянияmerge

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

  1. Создайте временный массивtemp, и три указателя:i(указывающий на текущий элемент левого массива),j(указывающий на текущий элемент правого массива),k(указывающий на позицию заполнения временного массива).
  2. Сравнениеleft[i]иright[j], затемменьшийпоместите этот элемент вtemp[k], затем соответствующий указатель иkПереместите на один шаг вперёд.
  3. Повторяйте шаг 2, пока все элементы одного из массивов не будут помещены во временный массив.
  4. Добавьте все оставшиеся элементы из другого массива (которые заведомо больше уже размещённых элементов и уже упорядочены) непосредственно в конец временного массива по порядку.
  5. временный массивtempУпорядоченная последовательность в ... копируется обратно в соответствующие позиции исходного массива.

Реализация кода и построчный анализ

Давайте реализуем сортировку слиянием на Python. Мы предоставим полную версию с подробными комментариями.

Тестовые данные

Сначала подготовим неупорядоченный список в качестве тестовых данных:

Пример

# Тестовые данные: неупорядоченный список целых чисел
test_array = [38, 27, 43, 3, 9, 82, 10]
print("Исходный массив:", test_array)

Полная реализация

Пример

def merge_sort(arr):
    """
Основная функция для сортировки слиянием.
Параметры:
arr (list): список, который нужно отсортировать.
Возвращает:
list: новый отсортированный список (для наглядности эта реализация возвращает новый список).
    """
    # Базовый случай: если длина массива равна 0 или 1, он уже отсортирован
    if len(arr) <= 1:
        return arr

    # 1. Разделение: находим середину и разбиваем массив на две половины
    mid = len(arr) // 2
    left_half = arr[:mid]  # Левая половина
    right_half = arr[mid:] # Правая половина

    # Рекурсивно отсортировать левую и правую половины
    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)

    # 2. Властвуй: объединить два отсортированных подмассива
    return merge(left_sorted, right_sorted)


def merge(left, right):
    """
Объединить два отсортированных списка.
Параметры:
left (list): Первый отсортированный список.
right (list): Второй отсортированный список.
Возвращает:
list: Объединённый отсортированный список.
    """
    sorted_list = []  # Временный список для хранения результата слияния
    i = j = 0         # i и j — указатели, проходящие по left и right соответственно

    # 3. Сравнение и слияние: пока в обоих списках ещё есть элементы
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # Примечание: используйте <= для сохранения устойчивости сортировки
            sorted_list.append(left[i])
            i += 1
        else:
            sorted_list.append(right[j])
            j += 1

    # 4. Обработать оставшиеся элементы: добавить все оставшиеся элементы из левого или правого списка в результат
    # Поскольку left и right уже отсортированы, все оставшиеся элементы должны быть больше уже объединённых элементов
    sorted_list.extend(left[i:])
    sorted_list.extend(right[j:])

    return sorted_list


# Запустить алгоритм на тестовых данных
sorted_array = merge_sort(test_array.copy())  # Используйте copy, чтобы не изменять исходный массив
print("После сортировки слиянием:", sorted_array)

Выполнение кода и вывод

Когда вы запустите приведённый выше код, вы увидите следующий вывод:

原始数组: [38, 27, 43, 3, 9, 82, 10]
归并排序后: [3, 9, 10, 27, 38, 43, 82]

Анализ алгоритма

Понимание эффективности алгоритма крайне важно. Мы обобщаем производительность сортировки слиянием в таблице ниже:

Метрика Сложность Описание
Временная сложность O(n log n) Это наиболее значительное преимущество сортировки слиянием.log nЭто обусловлено количеством уровней рекурсии (разделением массива пополам),nЭто связано с тем, что на каждом уровне операции слияния необходимо обойти все элементы. Независимо от исходного состояния данных (лучший, худший, средний случай), временная сложность составляет O(n log n).
Пространственная сложность O(n) Процесс слияния требует дополнительного пространства, равного по размеру исходному массиву, для хранения временных массивов. Это главный недостаток сортировки слиянием.
Стабильность Устойчивая ВmergeВ функции, когдаleft[i] == right[j]Когда это происходит, мы в первую очередь берёмleft[i](используя<=сравнение), что гарантирует, что исходный относительный порядок равных элементов остаётся неизменным.
Является ли она сортировкой на месте нет Она требует дополнительного объёма памяти.

Дополнительные примеры кода

Другие расширения