def merge(left, right):
    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
Пошагово:
i=0, j=0: 1 ≤ 2 → добавляем 1, result=[1]
i=1, j=0: 5 > 2 → добавляем 2, result=[1,2]
i=1, j=1: 5 > 3 → добавляем 3, result=[1,2,3]
i=1, j=2: 5 ≤ 7 → добавляем 5, result=[1,2,3,5]
Остались [8] и [7] → result=[1,2,3,5,7,8]
🎮 Практика
Базовый уровень 🟢
Задание 1: Слей два отсортированных массива [1, 4, 6] и [2, 3, 5, 8] вручную
<details>
<summary>💡 Подсказка</summary>
Используй два указателя и сравнивай элементы по порядку
</details>
<details>
<summary>✅ Ответ</summary>
[1, 2, 3, 4, 5, 6, 8]
</details>
Задание 2: Сколько уровней рекурсии потребуется для массива из 16 элементов?
<details>
<summary>💡 Подсказка</summary>
На каждом уровне размер массива уменьшается в 2 раза
</details>
<details>
<summary>✅ Ответ</summary>
log₂(16) = 4 уровня
</details>
Задание 3: Почему merge sort всегда работает за O(n log n), даже на уже отсортированном массиве?
<details>
<summary>💡 Подсказка</summary>
Алгоритм всегда делает одинаковое количество разделений и слияний
</details>
Задание 4: Реализуй функцию merge на Python для массивов [2, 7, 9] и [1, 6, 8, 10]
Продвинутый уровень 🟡
Задание 5: Сравни количество операций: merge sort vs bubble sort для n=1000
<details>
<summary>💡 Подсказка</summary>
Bubble sort: O(n²) ≈ 1,000,000 операций
Merge sort: O(n log n) ≈ 10,000 операций
</details>
Задание 6: Модифицируй merge sort для сортировки по убыванию
<details>
<summary>✅ Решение</summary>
Измени условие в функции merge: if left[i] >= right[j]
</details>
Задание 7: Оцени память, необходимую для сортировки массива из 1 миллиона int'ов
<details>
<summary>💡 Подсказка</summary>
Нужен дополнительный массив того же размера
</details>
Задание 8: Почему merge sort стабилен? Приведи пример
Челлендж 🔴
Задание 9: Реализуй итеративную (не рекурсивную) версию merge sort
<details>
<summary>💡 Подсказка</summary>
Начни с подмассивов размера 1, затем 2, 4, 8...
</details>
Задание 10: Оптимизируй merge sort: используй insertion sort для маленьких подмассивов (< 10 элементов)
Задание 11: Как использовать merge sort для подсчета инверсий в массиве?
⚠️ Частые ошибки
❌ Ошибка: Забывать добавлять оставшиеся элементы после основного цикла слияния
✅ Правильно: Всегда добавляй left[i:] и right[j:] в конце merge
💡 Почему: Один из массивов может закончиться раньше другого
❌ Ошибка: Думать, что merge sort экономит память
✅ Правильно: Merge sort требует O(n) дополнительной памяти
💡 Почему: Нужен temporary массив для слияния
❌ Ошибка: Использовать merge sort для маленьких массивов (< 50 элементов)
✅ Правильно: Для маленьких массивов лучше insertion sort
💡 Почему: Overhead рекурсии превышает выигрыш от O(n log n)
❌ Ошибка: Неправильно вычислять середину массива: mid = (left + right) / 2
✅ Правильно: mid = left + (right - left) // 2
💡 Почему: Избежать переполнения при больших индексах
🎓 Главное запомнить
✅ Суть: Разделяй массив пополам, сортируй части, сливай обратно
✅ Сложность: O(n log n) всегда - лучший универсальный алгоритм
✅ Применение: Большие данные, стабильная сортировка, внешняя сортировка
🔗 Связь с другими темами
Назад: Урок 267 заложил основы анализа алгоритмов - теперь видишь его на практике!
Вперед:
Быстрая сортировка (quicksort) - другой O(n log n) алгоритм
Внешняя сортировка - как сортировать файлы больше RAM
Map-Reduce - параллельная обработка данных по принципу "разделяй и властвуй"