Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

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

Сортировка слиянием (merge sort) - это алгоритм сортировки, основанный на стратегии «разделяй и властвуй», который включает этапы «разделения» и «слияния», показанные на рисунке 11-10.

1. Этап разделения: массив рекурсивно делится пополам, и задача сортировки длинного массива превращается в задачи сортировки более коротких массивов.
2. Этап слияния: когда длина подмассива становится равной 1, разделение завершается и начинается слияние. Два коротких упорядоченных массива непрерывно объединяются в один более длинный упорядоченный массив, пока процесс не завершится.

Рисунок 11-10 Этапы разделения и слияния в сортировке слиянием

## 11.6.1 Алгоритм

Как показано на рисунке 11-11, на этапе «разделения» массив рекурсивно разбивается сверху вниз по середине на два подмассива.

1. Вычислить середину массива `mid` и рекурсивно разделить левый подмассив (интервал `[left, mid]` ) и правый подмассив (интервал `[mid + 1, right]` ).
2. Рекурсивно повторять шаг `1.` , пока длина подмассива не станет равной 1.

Этап «слияния» снизу вверх объединяет левый и правый подмассивы в один упорядоченный массив. Следует заметить, что начиная с подмассивов длины 1, каждый подмассив в фазе слияния уже является упорядоченным.

<1><2><3><4><5><6><7><8><9><10>

Рисунок 11-11 Шаги сортировки слиянием

Нетрудно заметить, что порядок рекурсии в сортировке слиянием совпадает с порядком обхода в глубину двоичного дерева.

- Обход в глубину: сначала рекурсивно обходится левое поддерево, затем правое поддерево, а в конце обрабатывается корневой узел.
- Сортировка слиянием: сначала рекурсивно разделяется левый подмассив, затем правый подмассив, а в конце выполняется слияние.

Реализация сортировки слиянием показана в коде ниже. Обратите внимание: в `nums` объединяемый интервал равен `[left, right]` , а соответствующий интервал в `tmp` равен `[0, right - left]` .

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
merge_sort.py

    def merge(nums: list[int], left: int, mid: int, right: int):
        """Объединить левый и правый подмассивы"""
        # Диапазон левого подмассива: [left, mid], диапазон правого подмассива: [mid+1, right]
        # Создать временный массив tmp для хранения результата слияния
        tmp = [0] * (right - left + 1)
        # Инициализировать начальные индексы левого и правого подмассивов
        i, j, k = left, mid + 1, 0
        # Пока в левом и правом подмассивах еще есть элементы, сравнивать их и копировать меньший во временный массив
        while i <= mid and j <= right:
            if nums[i] <= nums[j]:
                tmp[k] = nums[i]
                i += 1
            else:
                tmp[k] = nums[j]
                j += 1
            k += 1
        # Скопировать оставшиеся элементы левого и правого подмассивов во временный массив
        while i <= mid:
            tmp[k] = nums[i]
            i += 1
            k += 1
        while j <= right:
            tmp[k] = nums[j]
            j += 1
            k += 1
        # Скопировать элементы временного массива tmp обратно в соответствующий диапазон исходного массива nums
        for k in range(0, len(tmp)):
            nums[left + k] = tmp[k]

    def merge_sort(nums: list[int], left: int, right: int):
        """Сортировка слиянием"""
        # Условие завершения
        if left >= right:
            return  # Завершить рекурсию, когда длина подмассива равна 1
        # Этап разбиения
        mid = (left + right) // 2 # Вычислить середину
        merge_sort(nums, left, mid)  # Рекурсивно обработать левый подмассив
        merge_sort(nums, mid + 1, right)  # Рекурсивно обработать правый подмассив
        # Этап слияния
        merge(nums, left, mid, right)

merge_sort.cpp

    /* Объединить левый и правый подмассивы */
    void merge(vector<int> &nums, int left, int mid, int right) {
        // Диапазон левого подмассива: [left, mid], диапазон правого подмассива: [mid+1, right]
        // Создать временный массив tmp для хранения результата слияния
        vector<int> tmp(right - left + 1);
        // Инициализировать начальные индексы левого и правого подмассивов
        int i = left, j = mid + 1, k = 0;
        // Пока в левом и правом подмассивах еще есть элементы, сравнивать их и копировать меньший во временный массив
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j])
                tmp[k++] = nums[i++];
            else
                tmp[k++] = nums[j++];
        }
        // Скопировать оставшиеся элементы левого и правого подмассивов во временный массив
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // Скопировать элементы временного массива tmp обратно в соответствующий диапазон исходного массива nums
        for (k = 0; k < tmp.size(); k++) {
            nums[left + k] = tmp[k];
        }
    }

    /* Сортировка слиянием */
    void mergeSort(vector<int> &nums, int left, int right) {
        // Условие завершения
        if (left >= right)
            return; // Завершить рекурсию, когда длина подмассива равна 1
        // Этап разбиения
        int mid = left + (right - left) / 2;    // Вычислить середину
        mergeSort(nums, left, mid);      // Рекурсивно обработать левый подмассив
        mergeSort(nums, mid + 1, right); // Рекурсивно обработать правый подмассив
        // Этап слияния
        merge(nums, left, mid, right);
    }

merge_sort.java

    /* Объединить левый и правый подмассивы */
    void merge(int[] nums, int left, int mid, int right) {
        // Диапазон левого подмассива: [left, mid], диапазон правого подмассива: [mid+1, right]
        // Создать временный массив tmp для хранения результата слияния
        int[] tmp = new int[right - left + 1];
        // Инициализировать начальные индексы левого и правого подмассивов
        int i = left, j = mid + 1, k = 0;
        // Пока в левом и правом подмассивах еще есть элементы, сравнивать их и копировать меньший во временный массив
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j])
                tmp[k++] = nums[i++];
            else
                tmp[k++] = nums[j++];
        }
        // Скопировать оставшиеся элементы левого и правого подмассивов во временный массив
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // Скопировать элементы временного массива tmp обратно в соответствующий диапазон исходного массива nums
        for (k = 0; k < tmp.length; k++) {
            nums[left + k] = tmp[k];
        }
    }

    /* Сортировка слиянием */
    void mergeSort(int[] nums, int left, int right) {
        // Условие завершения
        if (left >= right)
            return; // Завершить рекурсию, когда длина подмассива равна 1
        // Этап разбиения
        int mid = left + (right - left) / 2; // Вычислить середину
        mergeSort(nums, left, mid); // Рекурсивно обработать левый подмассив
        mergeSort(nums, mid + 1, right); // Рекурсивно обработать правый подмассив
        // Этап слияния
        merge(nums, left, mid, right);
    }

merge_sort.cs

    /* Объединить левый и правый подмассивы */
    void Merge(int[] nums, int left, int mid, int right) {
        // Диапазон левого подмассива: [left, mid], диапазон правого подмассива: [mid+1, right]
        // Создать временный массив tmp для хранения результата слияния
        int[] tmp = new int[right - left + 1];
        // Инициализировать начальные индексы левого и правого подмассивов
        int i = left, j = mid + 1, k = 0;
        // Пока в левом и правом подмассивах еще есть элементы, сравнивать их и копировать меньший во временный массив
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j])
                tmp[k++] = nums[i++];
            else
                tmp[k++] = nums[j++];
        }
        // Скопировать оставшиеся элементы левого и правого подмассивов во временный массив
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // Скопировать элементы временного массива tmp обратно в соответствующий диапазон исходного массива nums
        for (k = 0; k < tmp.Length; ++k) {
            nums[left + k] = tmp[k];
        }
    }

    /* Сортировка слиянием */
    void MergeSort(int[] nums, int left, int right) {
        // Условие завершения
        if (left >= right) return;       // Завершить рекурсию, когда длина подмассива равна 1
        // Этап разбиения
        int mid = left + (right - left) / 2;    // Вычислить середину
        MergeSort(nums, left, mid);      // Рекурсивно обработать левый подмассив
        MergeSort(nums, mid + 1, right); // Рекурсивно обработать правый подмассив
        // Этап слияния
        Merge(nums, left, mid, right);
    }

merge_sort.go

    /* Объединить левый и правый подмассивы */
    func merge(nums []int, left, mid, right int) {
        // Диапазон левого подмассива: [left, mid], диапазон правого подмассива: [mid+1, right]
        // Создать временный массив tmp для хранения результата слияния
        tmp := make([]int, right-left+1)
        // Инициализировать начальные индексы левого и правого подмассивов
        i, j, k := left, mid+1, 0
        // Пока в левом и правом подмассивах еще есть элементы, сравнивать их и копировать меньший во временный массив
        for i <= mid && j <= right {
            if nums[i] <= nums[j] {
                tmp[k] = nums[i]
                i++
            } else {
                tmp[k] = nums[j]
                j++
            }
            k++
        }
        // Скопировать оставшиеся элементы левого и правого подмассивов во временный массив
        for i <= mid {
            tmp[k] = nums[i]
            i++
            k++
        }
        for j <= right {
            tmp[k] = nums[j]
            j++
            k++
        }
        // Скопировать элементы временного массива tmp обратно в соответствующий диапазон исходного массива nums
        for k := 0; k < len(tmp); k++ {
            nums[left+k] = tmp[k]
        }
    }

    /* Сортировка слиянием */
    func mergeSort(nums []int, left, right int) {
        // Условие завершения
        if left >= right {
            return
        }
        // Этап разбиения
        mid := left + (right - left) / 2
        mergeSort(nums, left, mid)
        mergeSort(nums, mid+1, right)
        // Этап слияния
        merge(nums, left, mid, right)
    }

merge_sort.swift

    /* Объединить левый и правый подмассивы */
    func merge(nums: inout [Int], left: Int, mid: Int, right: Int) {
        // Диапазон левого подмассива: [left, mid], диапазон правого подмассива: [mid+1, right]
        // Создать временный массив tmp для хранения результата слияния
        var tmp = Array(repeating: 0, count: right - left + 1)
        // Инициализировать начальные индексы левого и правого подмассивов
        var i = left, j = mid + 1, k = 0
        // Пока в левом и правом подмассивах еще есть элементы, сравнивать их и копировать меньший во временный массив
        while i <= mid, j <= right {
            if nums[i] <= nums[j] {
                tmp[k] = nums[i]
                i += 1
            } else {
                tmp[k] = nums[j]
                j += 1
            }
            k += 1
        }
        // Скопировать оставшиеся элементы левого и правого подмассивов во временный массив
        while i <= mid {
            tmp[k] = nums[i]
            i += 1
            k += 1
        }
        while j <= right {
            tmp[k] = nums[j]
            j += 1
            k += 1
        }
        // Скопировать элементы временного массива tmp обратно в соответствующий диапазон исходного массива nums
        for k in tmp.indices {
            nums[left + k] = tmp[k]
        }
    }

    /* Сортировка слиянием */
    func mergeSort(nums: inout [Int], left: Int, right: Int) {
        // Условие завершения
        if left >= right { // Завершить рекурсию, когда длина подмассива равна 1
            return
        }
        // Этап разбиения
        let mid = left + (right - left) / 2 // Вычислить середину
        mergeSort(nums: &nums, left: left, right: mid) // Рекурсивно обработать левый подмассив
        mergeSort(nums: &nums, left: mid + 1, right: right) // Рекурсивно обработать правый подмассив
        // Этап слияния
        merge(nums: &nums, left: left, mid: mid, right: right)
    }

merge_sort.js

    /* Объединить левый и правый подмассивы */
    function merge(nums, left, mid, right) {
        // Диапазон левого подмассива: [left, mid], диапазон правого подмассива: [mid+1, right]
        // Создать временный массив tmp для хранения результата слияния
        const tmp = new Array(right - left + 1);
        // Инициализировать начальные индексы левого и правого подмассивов
        let i = left,
            j = mid + 1,
            k = 0;
        // Пока в левом и правом подмассивах еще есть элементы, сравнивать их и копировать меньший во временный массив
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }
        // Скопировать оставшиеся элементы левого и правого подмассивов во временный массив
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // Скопировать элементы временного массива tmp обратно в соответствующий диапазон исходного массива nums
        for (k = 0; k < tmp.length; k++) {
            nums[left + k] = tmp[k];
        }
    }

    /* Сортировка слиянием */
    function mergeSort(nums, left, right) {
        // Условие завершения
        if (left >= right) return; // Завершить рекурсию, когда длина подмассива равна 1
        // Этап разбиения
        let mid = Math.floor(left + (right - left) / 2); // Вычислить середину
        mergeSort(nums, left, mid); // Рекурсивно обработать левый подмассив
        mergeSort(nums, mid + 1, right); // Рекурсивно обработать правый подмассив
        // Этап слияния
        merge(nums, left, mid, right);
    }

merge_sort.ts

    /* Объединить левый и правый подмассивы */
    function merge(nums: number[], left: number, mid: number, right: number): void {
        // Диапазон левого подмассива: [left, mid], диапазон правого подмассива: [mid+1, right]
        // Создать временный массив tmp для хранения результата слияния
        const tmp = new Array(right - left + 1);
        // Инициализировать начальные индексы левого и правого подмассивов
        let i = left,
            j = mid + 1,
            k = 0;
        // Пока в левом и правом подмассивах еще есть элементы, сравнивать их и копировать меньший во временный массив
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }
        // Скопировать оставшиеся элементы левого и правого подмассивов во временный массив
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // Скопировать элементы временного массива tmp обратно в соответствующий диапазон исходного массива nums
        for (k = 0; k < tmp.length; k++) {
            nums[left + k] = tmp[k];
        }
    }

    /* Сортировка слиянием */
    function mergeSort(nums: number[], left: number, right: number): void {
        // Условие завершения
        if (left >= right) return; // Завершить рекурсию, когда длина подмассива равна 1
        // Этап разбиения
        let mid = Math.floor(left + (right - left) / 2); // Вычислить середину
        mergeSort(nums, left, mid); // Рекурсивно обработать левый подмассив
        mergeSort(nums, mid + 1, right); // Рекурсивно обработать правый подмассив
        // Этап слияния
        merge(nums, left, mid, right);
    }

merge_sort.dart

    /* Объединить левый и правый подмассивы */
    void merge(List<int> nums, int left, int mid, int right) {
      // Диапазон левого подмассива: [left, mid], диапазон правого подмассива: [mid+1, right]
      // Создать временный массив tmp для хранения результата слияния
      List<int> tmp = List.filled(right - left + 1, 0);
      // Инициализировать начальные индексы левого и правого подмассивов
      int i = left, j = mid + 1, k = 0;
      // Пока в левом и правом подмассивах еще есть элементы, сравнивать их и копировать меньший во временный массив
      while (i <= mid && j <= right) {
        if (nums[i] <= nums[j])
          tmp[k++] = nums[i++];
        else
          tmp[k++] = nums[j++];
      }
      // Скопировать оставшиеся элементы левого и правого подмассивов во временный массив
      while (i <= mid) {
        tmp[k++] = nums[i++];
      }
      while (j <= right) {
        tmp[k++] = nums[j++];
      }
      // Скопировать элементы временного массива tmp обратно в соответствующий диапазон исходного массива nums
      for (k = 0; k < tmp.length; k++) {
        nums[left + k] = tmp[k];
      }
    }

    /* Сортировка слиянием */
    void mergeSort(List<int> nums, int left, int right) {
      // Условие завершения
      if (left >= right) return; // Завершить рекурсию, когда длина подмассива равна 1
      // Этап разбиения
      int mid = left + (right - left) ~/ 2; // Вычислить середину
      mergeSort(nums, left, mid); // Рекурсивно обработать левый подмассив
      mergeSort(nums, mid + 1, right); // Рекурсивно обработать правый подмассив
      // Этап слияния
      merge(nums, left, mid, right);
    }

merge_sort.rs

    /* Объединить левый и правый подмассивы */
    fn merge(nums: &mut [i32], left: usize, mid: usize, right: usize) {
        // Диапазон левого подмассива: [left, mid], диапазон правого подмассива: [mid+1, right]
        // Создать временный массив tmp для хранения результата слияния
        let tmp_size = right - left + 1;
        let mut tmp = vec![0; tmp_size];
        // Инициализировать начальные индексы левого и правого подмассивов
        let (mut i, mut j, mut k) = (left, mid + 1, 0);
        // Пока в левом и правом подмассивах еще есть элементы, сравнивать их и копировать меньший во временный массив
        while i <= mid && j <= right {
            if nums[i] <= nums[j] {
                tmp[k] = nums[i];
                i += 1;
            } else {
                tmp[k] = nums[j];
                j += 1;
            }
            k += 1;
        }
        // Скопировать оставшиеся элементы левого и правого подмассивов во временный массив
        while i <= mid {
            tmp[k] = nums[i];
            k += 1;
            i += 1;
        }
        while j <= right {
            tmp[k] = nums[j];
            k += 1;
            j += 1;
        }
        // Скопировать элементы временного массива tmp обратно в соответствующий диапазон исходного массива nums
        for k in 0..tmp_size {
            nums[left + k] = tmp[k];
        }
    }

    /* Сортировка слиянием */
    fn merge_sort(nums: &mut [i32], left: usize, right: usize) {
        // Условие завершения
        if left >= right {
            return; // Завершить рекурсию, когда длина подмассива равна 1
        }

        // Этап разбиения
        let mid = left + (right - left) / 2; // Вычислить середину
        merge_sort(nums, left, mid); // Рекурсивно обработать левый подмассив
        merge_sort(nums, mid + 1, right); // Рекурсивно обработать правый подмассив

        // Этап слияния
        merge(nums, left, mid, right);
    }

merge_sort.c

    /* Объединить левый и правый подмассивы */
    void merge(int *nums, int left, int mid, int right) {
        // Диапазон левого подмассива: [left, mid], диапазон правого подмассива: [mid+1, right]
        // Создать временный массив tmp для хранения результата слияния
        int tmpSize = right - left + 1;
        int *tmp = (int *)malloc(tmpSize * sizeof(int));
        // Инициализировать начальные индексы левого и правого подмассивов
        int i = left, j = mid + 1, k = 0;
        // Пока в левом и правом подмассивах еще есть элементы, сравнивать их и копировать меньший во временный массив
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) {
                tmp[k++] = nums[i++];
            } else {
                tmp[k++] = nums[j++];
            }
        }
        // Скопировать оставшиеся элементы левого и правого подмассивов во временный массив
        while (i <= mid) {
            tmp[k++] = nums[i++];
        }
        while (j <= right) {
            tmp[k++] = nums[j++];
        }
        // Скопировать элементы временного массива tmp обратно в соответствующий диапазон исходного массива nums
        for (k = 0; k < tmpSize; ++k) {
            nums[left + k] = tmp[k];
        }
        // Освободить память
        free(tmp);
    }

    /* Сортировка слиянием */
    void mergeSort(int *nums, int left, int right) {
        // Условие завершения
        if (left >= right)
            return; // Завершить рекурсию, когда длина подмассива равна 1
        // Этап разбиения
        int mid = left + (right - left) / 2;    // Вычислить середину
        mergeSort(nums, left, mid);      // Рекурсивно обработать левый подмассив
        mergeSort(nums, mid + 1, right); // Рекурсивно обработать правый подмассив
        // Этап слияния
        merge(nums, left, mid, right);
    }

merge_sort.kt

    /* Объединить левый и правый подмассивы */
    fun merge(nums: IntArray, left: Int, mid: Int, right: Int) {
        // Диапазон левого подмассива: [left, mid], диапазон правого подмассива: [mid+1, right]
        // Создать временный массив tmp для хранения результата слияния
        val tmp = IntArray(right - left + 1)
        // Инициализировать начальные индексы левого и правого подмассивов
        var i = left
        var j = mid + 1
        var k = 0
        // Пока в левом и правом подмассивах еще есть элементы, сравнивать их и копировать меньший во временный массив
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j])
                tmp[k++] = nums[i++]
            else
                tmp[k++] = nums[j++]
        }
        // Скопировать оставшиеся элементы левого и правого подмассивов во временный массив
        while (i <= mid) {
            tmp[k++] = nums[i++]
        }
        while (j <= right) {
            tmp[k++] = nums[j++]
        }
        // Скопировать элементы временного массива tmp обратно в соответствующий диапазон исходного массива nums
        for (l in tmp.indices) {
            nums[left + l] = tmp[l]
        }
    }

    /* Сортировка слиянием */
    fun mergeSort(nums: IntArray, left: Int, right: Int) {
        // Условие завершения
        if (left >= right) return  // Завершить рекурсию, когда длина подмассива равна 1
        // Этап разбиения
        val mid = left + (right - left) / 2 // Вычислить середину
        mergeSort(nums, left, mid) // Рекурсивно обработать левый подмассив
        mergeSort(nums, mid + 1, right) // Рекурсивно обработать правый подмассив
        // Этап слияния
        merge(nums, left, mid, right)
    }

merge_sort.rb

    ### Слияние левого и правого подмассивов ###
    def merge(nums, left, mid, right)
      # Интервал левого подмассива: [left, mid], правого подмассива: [mid+1, right]
      # Создать временный массив tmp для хранения результата слияния
      tmp = Array.new(right - left + 1, 0)
      # Инициализировать начальные индексы левого и правого подмассивов
      i, j, k = left, mid + 1, 0
      # Пока в левом и правом подмассивах еще есть элементы, сравнивать их и копировать меньший во временный массив
      while i <= mid && j <= right
        if nums[i] <= nums[j]
          tmp[k] = nums[i]
          i += 1
        else
          tmp[k] = nums[j]
          j += 1
        end
        k += 1
      end
      # Скопировать оставшиеся элементы левого и правого подмассивов во временный массив
      while i <= mid
        tmp[k] = nums[i]
        i += 1
        k += 1
      end
      while j <= right
        tmp[k] = nums[j]
        j += 1
        k += 1
      end
      # Скопировать элементы временного массива tmp обратно в соответствующий диапазон исходного массива nums
      (0...tmp.length).each do |k|
        nums[left + k] = tmp[k]
      end
    end

    ### Сортировка слиянием ###
    def merge_sort(nums, left, right)
      # Условие завершения
      # Когда длина подмассива равна 1, рекурсия завершается
      return if left >= right
      # Этап разбиения
      mid = left + (right - left) / 2 # Вычислить середину
      merge_sort(nums, left, mid) # Рекурсивно обработать левый подмассив
      merge_sort(nums, mid + 1, right) # Рекурсивно обработать правый подмассив
      # Этап слияния
      merge(nums, left, mid, right)
    end

Визуализация кода

Во весь экран >

## 11.6.2 Характеристики алгоритма

- Временная сложность равна \(O(n \log n)\), алгоритм не является адаптивным: этап разделения создает дерево рекурсии высоты \(\log n\) , а суммарное число операций слияния на каждом уровне равно \(n\) , поэтому общая временная сложность составляет \(O(n \log n)\) .
- Пространственная сложность равна \(O(n)\), сортировка не выполняется на месте: глубина рекурсии равна \(\log n\) , из-за чего требуется \(O(\log n)\) памяти под стек вызовов. Для этапа слияния нужен вспомогательный массив, поэтому дополнительно используется \(O(n)\) памяти.
- Стабильная сортировка: в процессе слияния относительный порядок равных элементов не меняется.

## 11.6.3 Сортировка связного списка

Для связных списков сортировка слиянием имеет заметное преимущество перед другими алгоритмами сортировки: пространственную сложность задачи сортировки списка можно оптимизировать до \(O(1)\).

- Этап разделения: работу по разбиению списка можно реализовать с помощью «итерации» вместо «рекурсии», тем самым устранив расход памяти на стек вызовов.
- Этап слияния: в связном списке добавление и удаление узлов требует только изменения ссылок (указателей), поэтому при слиянии двух коротких упорядоченных списков в один длинный упорядоченный список не нужно создавать дополнительный список.

Детали реализации достаточно сложны. Заинтересованные читатели могут обратиться к соответствующим материалам самостоятельно.

##### Оставляйте свои идеи, вопросы и предложения в комментариях