Перейти к содержанию

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, каждый подмассив в фазе слияния уже является упорядоченным.

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

merge_sort_step2

merge_sort_step3

merge_sort_step4

merge_sort_step5

merge_sort_step6

merge_sort_step7

merge_sort_step8

merge_sort_step9

merge_sort_step10

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

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

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

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

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)\).

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

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

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