Сортировка слиянием (Merge Sort): полное руководство с примерами

Почему сортировка слиянием важна?

Сортировка слиянием (Merge Sort) — один из фундаментальных алгоритмов, который должен знать каждый программист:

• 🎯 Гарантированная сложность O(n log n) в любом случае — лучший, средний и худший
• 🔒 Стабильный алгоритм — сохраняет относительный порядок равных элементов
• 📚 Основа для понимания принципа "разделяй и властвуй"
• 💾 Идеален для сортировки связных списков и внешней сортировки
• 💼 Обязательный вопрос на собеседованиях в FAANG компаниях

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

Merge Sort — это алгоритм сортировки, основанный на принципе "разделяй и властвуй" (divide and conquer). Алгоритм был изобретен Джоном фон Нейманом в 1945 году.

Принцип работы:

1. Разделение (Divide): Рекурсивно делим массив пополам, пока не получим подмассивы из одного элемента
2. Завоевание (Conquer): Массив из одного элемента считается отсортированным
3. Слияние (Merge): Объединяем два отсортированных подмассива в один отсортированный массив

Визуализация работы алгоритма:

// Исходный массив: [38, 27, 43, 3, 9, 82, 10]

// Шаг 1: Разделение
//                [38, 27, 43, 3, 9, 82, 10]
//                /                        \
//        [38, 27, 43, 3]            [9, 82, 10]
//         /          \              /         \
//    [38, 27]      [43, 3]      [9, 82]      [10]
//     /    \        /    \       /    \
//  [38]   [27]   [43]   [3]   [9]   [82]

// Шаг 2: Слияние (снизу вверх)
//  [27, 38]   [3, 43]   [9, 82]   [10]
//       \      /            \      /
//    [3, 27, 38, 43]     [9, 10, 82]
//            \               /
//      [3, 9, 10, 27, 38, 43, 82]

Реализации Merge Sort на JavaScript

Решение 1: Классическая рекурсивная реализация

function mergeSort(arr) {
  // Базовый случай: массив из 0 или 1 элемента уже отсортирован
  if (arr.length <= 1) {
    return arr;
  }

  // Находим середину массива
  const mid = Math.floor(arr.length / 2);

  // Рекурсивно сортируем левую и правую половины
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  // Сливаем отсортированные половины
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  // Сравниваем элементы из обоих массивов и добавляем меньший
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // Добавляем оставшиеся элементы
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// Пример использования
const array = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(array)); // [3, 9, 10, 27, 38, 43, 82]

Анализ решения:

• Простая и понятная реализация
• Создает новые массивы на каждом уровне рекурсии
• Легко читается и поддерживается
• Использует O(n) дополнительной памяти

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Решение 2: Оптимизированная версия с меньшим количеством копирований

function mergeSortOptimized(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSortOptimized(arr.slice(0, mid));
  const right = mergeSortOptimized(arr.slice(mid));

  return mergeOptimized(left, right);
}

function mergeOptimized(left, right) {
  const result = new Array(left.length + right.length);
  let i = 0,
    j = 0,
    k = 0;

  while (i < left.length && j < right.length) {
    result[k++] = left[i] <= right[j] ? left[i++] : right[j++];
  }

  while (i < left.length) {
    result[k++] = left[i++];
  }

  while (j < right.length) {
    result[k++] = right[j++];
  }

  return result;
}

// Пример использования
const array = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSortOptimized(array)); // [3, 9, 10, 27, 38, 43, 82]

Преимущества:

• Заранее выделяем память нужного размера
• Избегаем множественных вызовов concat()
• Немного быстрее на больших массивах

Решение 3: In-place Merge Sort (сортировка на месте)

function mergeSortInPlace(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    const mid = Math.floor((left + right) / 2);

    // Рекурсивно сортируем обе половины
    mergeSortInPlace(arr, left, mid);
    mergeSortInPlace(arr, mid + 1, right);

    // Сливаем на месте
    mergeInPlace(arr, left, mid, right);
  }

  return arr;
}

function mergeInPlace(arr, left, mid, right) {
  // Создаем временные массивы
  const leftArr = arr.slice(left, mid + 1);
  const rightArr = arr.slice(mid + 1, right + 1);

  let i = 0,
    j = 0,
    k = left;

  while (i < leftArr.length && j < rightArr.length) {
    if (leftArr[i] <= rightArr[j]) {
      arr[k++] = leftArr[i++];
    } else {
      arr[k++] = rightArr[j++];
    }
  }

  while (i < leftArr.length) {
    arr[k++] = leftArr[i++];
  }

  while (j < rightArr.length) {
    arr[k++] = rightArr[j++];
  }
}

// Пример использования
const array = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSortInPlace(array)); // [3, 9, 10, 27, 38, 43, 82]

Особенности:

• Модифицирует исходный массив
• Использует индексы вместо создания новых массивов
• Все еще требует O(n) временной памяти для слияния

Решение 4: Итеративный Merge Sort (Bottom-Up)

function mergeSortIterative(arr) {
  const n = arr.length;

  // Начинаем с подмассивов размером 1, затем 2, 4, 8...
  for (let size = 1; size < n; size *= 2) {
    // Проходим по всем парам подмассивов текущего размера
    for (let leftStart = 0; leftStart < n - 1; leftStart += 2 * size) {
      const mid = Math.min(leftStart + size - 1, n - 1);
      const rightEnd = Math.min(leftStart + 2 * size - 1, n - 1);

      mergeIterative(arr, leftStart, mid, rightEnd);
    }
  }

  return arr;
}

function mergeIterative(arr, left, mid, right) {
  const leftArr = arr.slice(left, mid + 1);
  const rightArr = arr.slice(mid + 1, right + 1);

  let i = 0,
    j = 0,
    k = left;

  while (i < leftArr.length && j < rightArr.length) {
    arr[k++] = leftArr[i] <= rightArr[j] ? leftArr[i++] : rightArr[j++];
  }

  while (i < leftArr.length) arr[k++] = leftArr[i++];
  while (j < rightArr.length) arr[k++] = rightArr[j++];
}

// Пример использования
const array = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSortIterative(array)); // [3, 9, 10, 27, 38, 43, 82]

Преимущества итеративного подхода:

• Нет риска переполнения стека вызовов
• Более предсказуемое использование памяти
• Легче оптимизировать для параллельного выполнения

Реализация на Python

Классическая реализация

def merge_sort(arr: list) -> list:
    """
    Сортировка слиянием (рекурсивная)

    Args:
        arr: Массив для сортировки

    Returns:
        Отсортированный массив
    """
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2

    # Рекурсивно сортируем обе половины
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # Сливаем отсортированные половины
    return merge(left, right)


def merge(left: list, right: list) -> list:
    """
    Слияние двух отсортированных массивов

    Args:
        left: Левый отсортированный массив
        right: Правый отсортированный массив

    Returns:
        Объединенный отсортированный массив
    """
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # Добавляем оставшиеся элементы
    result.extend(left[i:])
    result.extend(right[j:])

    return result


# Пример использования
array = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(array))  # [3, 9, 10, 27, 38, 43, 82]

Python: In-place версия

def merge_sort_inplace(arr: list, left: int = 0, right: int = None) -> list:
    """Сортировка слиянием на месте"""
    if right is None:
        right = len(arr) - 1

    if left < right:
        mid = (left + right) // 2

        merge_sort_inplace(arr, left, mid)
        merge_sort_inplace(arr, mid + 1, right)

        merge_inplace(arr, left, mid, right)

    return arr


def merge_inplace(arr: list, left: int, mid: int, right: int) -> None:
    """Слияние двух частей массива на месте"""
    # Создаем копии подмассивов
    left_arr = arr[left:mid + 1]
    right_arr = arr[mid + 1:right + 1]

    i = j = 0
    k = left

    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] <= right_arr[j]:
            arr[k] = left_arr[i]
            i += 1
        else:
            arr[k] = right_arr[j]
            j += 1
        k += 1

    # Копируем оставшиеся элементы
    while i < len(left_arr):
        arr[k] = left_arr[i]
        i += 1
        k += 1

    while j < len(right_arr):
        arr[k] = right_arr[j]
        j += 1
        k += 1


# Пример использования
array = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort_inplace(array))  # [3, 9, 10, 27, 38, 43, 82]

Python: Итеративная версия (Bottom-Up)

def merge_sort_iterative(arr: list) -> list:
    """Итеративная сортировка слиянием (снизу вверх)"""
    n = len(arr)
    size = 1

    while size < n:
        for left in range(0, n - 1, 2 * size):
            mid = min(left + size - 1, n - 1)
            right = min(left + 2 * size - 1, n - 1)

            merge_inplace(arr, left, mid, right)

        size *= 2

    return arr


# Пример использования
array = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort_iterative(array))  # [3, 9, 10, 27, 38, 43, 82]

Временная и пространственная сложность

Временная сложность

Почему O(n log n)?

// Глубина рекурсии: log n (делим массив пополам на каждом уровне)
// Работа на каждом уровне: O(n) (сливаем все элементы)
// Итого: O(n) * O(log n) = O(n log n)

// Визуализация для массива из 8 элементов:
// Уровень 0: 1 массив из 8 элементов   -> 8 операций слияния
// Уровень 1: 2 массива по 4 элемента   -> 8 операций слияния
// Уровень 2: 4 массива по 2 элемента   -> 8 операций слияния
// Уровень 3: 8 массивов по 1 элементу  -> базовый случай

// Всего: 3 уровня * 8 операций = 24 = 8 * log2(8)

Пространственная сложность

• O(n) — для хранения временных массивов при слиянии
• O(log n) — для стека рекурсии

Сравнение с другими алгоритмами сортировки

Когда выбирать Merge Sort?

Используйте Merge Sort когда:

• Нужна гарантированная сложность O(n log n)
• Важна стабильность сортировки
• Сортируете связные списки (не требует произвольного доступа)
• Выполняете внешнюю сортировку больших файлов
• Данные поступают последовательно (streaming)

Не используйте Merge Sort когда:

• Критична память (Quick Sort использует меньше)
• Массив почти отсортирован (Insertion Sort быстрее)
• Нужна сортировка на месте без доп. памяти

Merge Sort для связных списков

Одно из главных преимуществ Merge Sort — эффективность для связных списков:

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

function mergeSortLinkedList(head) {
  // Базовый случай: пустой список или один элемент
  if (!head || !head.next) {
    return head;
  }

  // Находим середину списка
  const mid = getMiddle(head);
  const rightHead = mid.next;
  mid.next = null; // Разрываем связь

  // Рекурсивно сортируем обе половины
  const left = mergeSortLinkedList(head);
  const right = mergeSortLinkedList(rightHead);

  // Сливаем отсортированные половины
  return mergeLinkedLists(left, right);
}

function getMiddle(head) {
  let slow = head;
  let fast = head.next;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  return slow;
}

function mergeLinkedLists(left, right) {
  const dummy = new ListNode(0);
  let current = dummy;

  while (left && right) {
    if (left.val <= right.val) {
      current.next = left;
      left = left.next;
    } else {
      current.next = right;
      right = right.next;
    }
    current = current.next;
  }

  current.next = left || right;

  return dummy.next;
}

Почему Merge Sort идеален для связных списков:

• Не требует произвольного доступа к элементам
• Слияние выполняется за O(1) дополнительной памяти
• Разделение списка пополам — O(n)

Применение: подсчет инверсий

Merge Sort можно использовать для подсчета инверсий в массиве — пар элементов, где больший элемент стоит раньше меньшего:

function countInversions(arr) {
  let inversions = 0;

  function mergeSort(arr) {
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
  }

  function merge(left, right) {
    const result = [];
    let i = 0,
      j = 0;

    while (i < left.length && j < right.length) {
      if (left[i] <= right[j]) {
        result.push(left[i++]);
      } else {
        // Все оставшиеся элементы в left больше right[j]
        inversions += left.length - i;
        result.push(right[j++]);
      }
    }

    return result.concat(left.slice(i)).concat(right.slice(j));
  }

  mergeSort(arr);
  return inversions;
}

// Пример: [2, 4, 1, 3, 5]
// Инверсии: (2,1), (4,1), (4,3) = 3
console.log(countInversions([2, 4, 1, 3, 5])); // 3

Распространенные ошибки

1. Неправильное вычисление середины: Используйте Math.floor((left + right) / 2) вместо (left + right) / 2

2. Забытые элементы при слиянии: Не забудьте добавить оставшиеся элементы из обоих массивов

3. Бесконечная рекурсия: Убедитесь, что базовый случай arr.length <= 1 обрабатывается корректно

4. Нестабильное слияние: Используйте <= вместо < для сохранения стабильности

Практические применения

Где используется Merge Sort?

• Timsort (Python, Java) — гибрид Merge Sort и Insertion Sort
• Внешняя сортировка — сортировка данных, не помещающихся в память
• Параллельные вычисления — легко распараллеливается
• Git — для слияния изменений в файлах
• Базы данных — для сортировки больших наборов данных

Timsort: практическая эволюция Merge Sort

// Timsort использует идеи Merge Sort с оптимизациями:
// 1. Использует Insertion Sort для малых подмассивов (runs)
// 2. Ищет естественные "runs" — уже отсортированные участки
// 3. Сливает runs с учетом их размеров

// Python: sorted() и list.sort() используют Timsort
// Java: Arrays.sort() для объектов использует Timsort

Заключение

Сортировка слиянием — это фундаментальный алгоритм с уникальными преимуществами:

• Гарантированная сложность O(n log n) в любом случае
• Стабильность — сохраняет порядок равных элементов
• Идеален для связных списков и внешней сортировки
• Легко распараллеливается
• Основа для продвинутых алгоритмов (Timsort)

Понимание Merge Sort критически важно для любого разработчика — этот алгоритм не только часто встречается на собеседованиях, но и лежит в основе многих практических систем обработки данных.