PrepBro
← Назад к вопросам

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

2.0 Middle🔥 131 комментариев
#Python Core#Архитектура и паттерны

Условие

Реализуйте алгоритм сортировки слиянием (Merge Sort).

Это рекурсивный алгоритм "разделяй и властвуй" со сложностью O(n log n).

Пример

merge_sort([38, 27, 43, 3, 9, 82, 10]) → [3, 9, 10, 27, 38, 43, 82]

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

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

Сортировка слиянием — это эффективный рекурсивный алгоритм сортировки, основанный на парадигме «разделяй и властвуй». Алгоритм разделяет массив пополам, рекурсивно сортирует каждую половину, а затем объединяет отсортированные половины в один отсортированный массив.

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

def merge_sort(arr: list) -> list:
    """
    Сортировка слиянием.
    
    Args:
        arr: Массив для сортировки
    
    Returns:
        Отсортированный массив
    
    Временная сложность: O(n log n)
    Пространственная сложность: O(n)
    """
    if len(arr) <= 1:
        return arr
    
    # Разделяем массив пополам
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    # Рекурсивно сортируем обе половины
    left_sorted = merge_sort(left)
    right_sorted = merge_sort(right)
    
    # Объединяем отсортированные половины
    return merge(left_sorted, right_sorted)

def merge(left: list, right: list) -> list:
    """
    Объединяет два отсортированных массива в один отсортированный.
    """
    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

# Тестирование
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))  # [3, 9, 10, 27, 38, 43, 82]
print(merge_sort([5, 2, 8, 1, 9]))              # [1, 2, 5, 8, 9]
print(merge_sort([1]))                          # [1]
print(merge_sort([]))                           # []

Решение 2: Инplace сортировка (минимизация памяти)

def merge_sort_inplace(arr: list, left: int = 0, right: int = None) -> None:
    """
    Сортировка слиянием с минимальным использованием дополнительной памяти.
    Модифицирует массив на месте.
    """
    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)

def merge_inplace(arr: list, left: int, mid: int, right: int) -> None:
    """
    Объединяет два отсортированных подмассива на месте.
    """
    # Создаём временные копии
    left_half = arr[left:mid + 1]
    right_half = arr[mid + 1:right + 1]
    
    i = j = 0
    k = left
    
    # Объединяем половины
    while i < len(left_half) and j < len(right_half):
        if left_half[i] <= right_half[j]:
            arr[k] = left_half[i]
            i += 1
        else:
            arr[k] = right_half[j]
            j += 1
        k += 1
    
    # Копируем оставшиеся элементы
    while i < len(left_half):
        arr[k] = left_half[i]
        i += 1
        k += 1
    
    while j < len(right_half):
        arr[k] = right_half[j]
        j += 1
        k += 1

# Тестирование
arr = [38, 27, 43, 3, 9, 82, 10]
merge_sort_inplace(arr)
print(arr)  # [3, 9, 10, 27, 38, 43, 82]

Решение 3: С визуализацией процесса

def merge_sort_verbose(arr: list, depth: int = 0) -> list:
    """
    Сортировка слиянием с визуализацией процесса.
    """
    indent = "  " * depth
    print(f"{indent}Разделяем: {arr}")
    
    if len(arr) <= 1:
        print(f"{indent}Базовый случай: {arr}")
        return arr
    
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    print(f"{indent}Левая половина: {left}")
    print(f"{indent}Правая половина: {right}")
    
    left_sorted = merge_sort_verbose(left, depth + 1)
    right_sorted = merge_sort_verbose(right, depth + 1)
    
    result = merge(left_sorted, right_sorted)
    print(f"{indent}Объединили: {result}")
    
    return result

# Пример
merge_sort_verbose([38, 27, 43, 3])

Решение 4: Сортировка списков объектов

from typing import List, Callable, Any

def merge_sort_by_key(arr: List[Any], key: Callable = None) -> List[Any]:
    """
    Сортировка слиянием с кастомной функцией сравнения.
    """
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    
    left_sorted = merge_sort_by_key(left, key)
    right_sorted = merge_sort_by_key(right, key)
    
    return merge_by_key(left_sorted, right_sorted, key)

def merge_by_key(left: list, right: list, key: Callable = None) -> list:
    """
    Объединение с кастомной функцией сравнения.
    """
    result = []
    i = j = 0
    
    while i < len(left) and j < len(right):
        left_val = key(left[i]) if key else left[i]
        right_val = key(right[j]) if key else right[j]
        
        if left_val <= right_val:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Тестирование с объектами
students = [
    {'name': 'Alice', 'score': 85},
    {'name': 'Bob', 'score': 75},
    {'name': 'Charlie', 'score': 95},
]

sorted_students = merge_sort_by_key(students, key=lambda x: x['score'])
for student in sorted_students:
    print(f"{student['name']}: {student['score']}")
# Bob: 75
# Alice: 85
# Charlie: 95

Решение 5: Сортировка с подсчётом инверсий

def merge_sort_count_inversions(arr: list) -> tuple:
    """
    Сортировка слиянием с подсчётом количества инверсий.
    Инверсия — пара индексов (i, j) где i < j, но arr[i] > arr[j].
    """
    def merge_and_count(left: list, right: list) -> tuple:
        result = []
        inversions = 0
        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])
                # Все элементы в left[i:] больше right[j]
                inversions += len(left) - i
                j += 1
        
        result.extend(left[i:])
        result.extend(right[j:])
        return result, inversions
    
    def sort_and_count(arr: list) -> tuple:
        if len(arr) <= 1:
            return arr, 0
        
        mid = len(arr) // 2
        left, left_inv = sort_and_count(arr[:mid])
        right, right_inv = sort_and_count(arr[mid:])
        merged, merge_inv = merge_and_count(left, right)
        
        return merged, left_inv + right_inv + merge_inv
    
    return sort_and_count(arr)

# Тестирование
arr = [1, 3, 5, 2, 4, 6]
sorted_arr, inversions = merge_sort_count_inversions(arr)
print(f"Отсортировано: {sorted_arr}")
print(f"Инверсии: {inversions}")  # 3 инверсии: (3,2), (5,2), (5,4)

Полное решение с тестами

def merge_sort(arr: list) -> list:
    """
    Сортировка слиянием.
    
    Использует парадигму "разделяй и властвуй":
    1. Разделяем массив пополам
    2. Рекурсивно сортируем обе половины
    3. Объединяем отсортированные половины
    
    Временная сложность: O(n log n) во всех случаях
    Пространственная сложность: O(n)
    Стабильна: Да (равные элементы сохраняют порядок)
    """
    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:
    """Объединяет два отсортированных массива."""
    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

def test_merge_sort():
    # Основные тесты
    assert merge_sort([38, 27, 43, 3, 9, 82, 10]) == [3, 9, 10, 27, 38, 43, 82]
    assert merge_sort([5, 2, 8, 1, 9]) == [1, 2, 5, 8, 9]
    
    # Граничные случаи
    assert merge_sort([]) == []
    assert merge_sort([1]) == [1]
    assert merge_sort([2, 1]) == [1, 2]
    
    # Уже отсортированный
    assert merge_sort([1, 2, 3, 4, 5]) == [1, 2, 3, 4, 5]
    
    # Обратный порядок
    assert merge_sort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]
    
    # Дубликаты
    assert merge_sort([3, 1, 2, 1, 3]) == [1, 1, 2, 3, 3]
    
    # Отрицательные числа
    assert merge_sort([3, -1, 2, -2, 0]) == [-2, -1, 0, 2, 3]
    
    print("✓ Все тесты пройдены!")

test_merge_sort()

Анализ сложности

ПараметрЗначение
Лучший случайO(n log n)
Средний случайO(n log n)
Худший случайO(n log n)
ПространствоO(n)
СтабильностьДа
АдаптивностьНет

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

АлгоритмЛучшеХудшеПамять
Quick SortO(n log n)O(n²)O(log n)
Merge SortO(n log n)O(n log n)O(n)
Heap SortO(n log n)O(n log n)O(1)
Bubble SortO(n)O(n²)O(1)

Преимущества и недостатки

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

  • Гарантированная O(n log n) — всегда стабильная производительность
  • Стабильна — сохраняет порядок равных элементов
  • Параллелизм — можно распараллелить
  • Предсказуемо — не зависит от входных данных

Недостатки:

  • Требует O(n) дополнительной памяти — неинplace алгоритм
  • Медленнее Quick Sort в среднем — на реальных данных
  • Не адаптивна — одинаково медленна для отсортированных данных

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

  • Встроенная сортировка в Python — TimSort основан на Merge Sort
  • Сортировка в Java — Arrays.sort() для объектов
  • Дисковые файлы — если данные не помещаются в памяти
  • Подсчёт инверсий — в анализе данных
  • Внешняя сортировка — для больших объёмов данных