Сортировка слиянием: разделить, отсортировать, объединить
Реализуйте сортировку слиянием рекурсивно, проследите за деревом «разделяй и властвуй» и объясните, почему она гарантирует O(n log n) во всех случаях
«Сортировка слиянием: разделить, отсортировать, объединить» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.
Интуиция метода «разделяй и властвуй»
Сортировка слиянием — классический алгоритм «разделяй и властвуй»: разделите массив пополам, рекурсивно отсортируйте каждую половину, затем объедините две отсортированные половины в один отсортированный результат. Ключевая идея состоит в том, что слияние двух отсортированных массивов занимает O(n) — намного меньше, чем сортировка с нуля. Такое разбиение создаёт дерево рекурсии с log n уровнями, каждый из которых требует O(n) работы для слияния, что даёт оптимальную нижнюю границу для сортировки сравнениями — O(n log n).
# High-level merge sort structure
def merge_sort(arr):
# Base case: 0 or 1 element already sorted
if len(arr) <= 1:
return arr
# Divide
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
# Conquer (merge)
return merge(left, right)
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]Объяснение шага слияния
При слиянии двух отсортированных массивов поддерживайте два указателя — по одному для каждой половины. Сравнивайте первые элементы; копируйте меньший из них в выходной массив и сдвигайте соответствующий указатель. Когда одна половина закончится, напрямую скопируйте остаток другой половины. Это занимает O(n) времени и O(n) памяти для выходного массива. Шаг слияния — алгоритмическое ядро сортировки слиянием, поэтому разберитесь в нём досконально.
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= preserves stability
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Append remaining elements
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge([1,3,5,7], [2,4,6,8]))
# [1, 2, 3, 4, 5, 6, 7, 8]Полная реализация сортировки слиянием
Объединение разбиения и слияния: рекурсивные вызовы делят задачу пополам, пока не останутся отдельные элементы (которые тривиально отсортированы), затем вызовы слияния объединяют их обратно. На каждом уровне дерева рекурсии сливаются в общей сложности одни и те же n элементов (распределённые между несколькими операциями слияния). Глубина рекурсии равна log₂(n), поэтому общее время составляет O(n log n), а вспомогательная память — O(n) для массивов результатов слияния плюс глубина стека вызовов O(log n).
def merge_sort_full(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_full(arr[:mid])
right = merge_sort_full(arr[mid:])
# Merge the two sorted halves
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: merged.append(left[i]); i += 1
else: merged.append(right[j]); j += 1
merged.extend(left[i:] + right[j:])
return merged
print(merge_sort_full([5,2,4,6,1,3,2,6]))
# [1, 2, 2, 3, 4, 5, 6, 6]Дерево рекурсии сортировки слиянием
Представьте дерево рекурсии сортировки слиянием для n=8: на уровне 0 находится один массив из 8 элементов; на уровне 1 — два массива по 4 элемента; на уровне 2 — четыре массива по 2 элемента; на уровне 3 — восемь отдельных элементов (базовые случаи). При обратном движении вверх слияние на уровнях 3→2 обрабатывает в общей сложности 8 элементов, на уровнях 2→1 — также 8, а на уровнях 1→0 — ещё 8. Итого 3 уровня × 8 элементов = 24 операции ≈ 8 × log₂(8) = 24. Это подтверждает оценку O(n log n).
# Trace the tree depth
level_work = []
def merge_sort_traced(arr, depth=0):
if depth >= len(level_work):
level_work.append(0)
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_traced(arr[:mid], depth+1)
right = merge_sort_traced(arr[mid:], depth+1)
level_work[depth] += len(arr) # track merge work
merged = sorted(left + right) # simplified merge
return merged
merge_sort_traced(list(range(8, 0, -1)))
for d, work in enumerate(level_work):
print(f'Level {d}: {work} elements merged')Сортировка слиянием на месте
Стандартная рекурсивная сортировка слиянием выделяет вспомогательную память O(n) для результата слияния. Существует сортировка слиянием на месте, но она сложна и имеет большие константные множители — на собеседованиях о ней спрашивают редко. Частый дополнительный вопрос на собеседовании: «Можно ли реализовать сортировку слиянием с дополнительной памятью O(1)?» Правильный ответ: «В теории да, но практические реализации либо используют память O(n), либо значительно усложняются; Тимсорт в Python использует память O(n) для слияния».
# Bottom-up merge sort: iterative, avoids recursion stack
def merge_sort_bottomup(arr):
n = len(arr)
width = 1
while width < n:
for i in range(0, n, 2 * width):
left = arr[i:i+width]
right = arr[i+width:i+2*width]
# Merge and put back
merged = []
a, b = 0, 0
while a < len(left) and b < len(right):
if left[a] <= right[b]: merged.append(left[a]); a+=1
else: merged.append(right[b]); b+=1
merged += left[a:] + right[b:]
arr[i:i+len(merged)] = merged
width *= 2
return arr
print(merge_sort_bottomup([5,2,4,6,1,3]))
# [1, 2, 3, 4, 5, 6]Сортировка слиянием стабильна
Сортировка слиянием стабильна: одинаковые элементы из левой половины всегда располагаются перед одинаковыми элементами из правой половины в объединённом результате. Это гарантируется использованием <= (а не <) при выборе левого элемента. Стабильность важна при сортировке по нескольким ключам. Встроенные в Python функции sorted() и list.sort() используют Тимсорт, который также стабилен и работает за O(n log n), поэтому это безопасный выбор для любого промышленного кода.
# Demonstrating stability: sort (value, original_index) pairs
items = [(3,'A'), (1,'B'), (3,'C'), (2,'D')]
# Sort by value only
result = merge_sort_full(items) # won't work directly
# Use Python's stable sort:
result = sorted(items, key=lambda x: x[0])
print(result)
# [(1,'B'),(2,'D'),(3,'A'),(3,'C')]
# 'A' comes before 'C' for value=3 (stable order)Слияние k отсортированных массивов
Слияние k отсортированных массивов с общим числом n элементов можно выполнять, последовательно сливая пары (подобно турнирной сетке), за O(n log k). На каждом уровне слияния обрабатывается n элементов, а уровней всего log k. Другой вариант — использовать минимальную кучу размера k: добавить в неё наименьший оставшийся элемент из каждого массива, извлечь минимум и добавить следующий элемент из того же массива. Этот подход также работает за O(n log k), но использует память эффективнее, когда k очень велико.
import heapq
def merge_k_sorted(arrays):
result = []
heap = []
# Push first element from each array with array index
for i, arr in enumerate(arrays):
if arr:
heapq.heappush(heap, (arr[0], i, 0))
while heap:
val, arr_i, elem_i = heapq.heappop(heap)
result.append(val)
if elem_i + 1 < len(arrays[arr_i]):
next_val = arrays[arr_i][elem_i + 1]
heapq.heappush(heap, (next_val, arr_i, elem_i+1))
return result
arrs = [[1,4,7],[2,5,8],[3,6,9]]
print(merge_k_sorted(arrs)) # [1,2,3,4,5,6,7,8,9]Подсчёт инверсий с помощью сортировки слиянием
Подсчёт инверсий (пар, для которых a[i] > a[j] и i < j) за O(n log n) выполняется с помощью модифицированной сортировки слиянием. На этапе слияния, когда элемент из правого подмассива меньше элемента из левого подмассива, он образует инверсию с каждым оставшимся элементом левого подмассива. В этот момент добавьте len(left) - i к счётчику.
def count_inversions(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, l_inv = count_inversions(arr[:mid])
right, r_inv = count_inversions(arr[mid:])
merged = []
inversions = l_inv + r_inv
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
inversions += len(left) - i # all remaining left elements > right[j]
merged.extend(left[i:] + right[j:])
return merged, inversions
_, inv = count_inversions([3, 1, 2])
print(inv) # 2: (3,1) and (3,2)Сортировка слиянием и быстрая сортировка
Сортировка слиянием гарантирует O(n log n) во всех случаях, является стабильной и лучше подходит для связанных списков и внешней сортировки. Быстрая сортировка в среднем работает за O(n log n), но в худшем случае — за O(n²); она выполняется на месте (используя O(log n) памяти стека) и часто быстрее на практике благодаря эффективному использованию кэша при работе с массивами. Встроенная сортировка Python использует Тимсорт (разновидность сортировки слиянием) — это всегда правильный выбор по умолчанию.
# Head-to-head complexity comparison:
# Algorithm | Best | Avg | Worst | Space | Stable
# Bubble sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Insertion sort| O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Merge sort | O(nlogn)| O(nlogn)| O(nlogn)| O(n) | Yes
# Quick sort | O(nlogn)| O(nlogn)| O(n^2) | O(logn)| No
# Heap sort | O(nlogn)| O(nlogn)| O(nlogn)| O(1) | No
print('Merge sort: stable, O(n log n) guaranteed, O(n) space')Внешняя сортировка: сортировка слиянием при больших объёмах данных
Сортировка слиянием лежит в основе внешней сортировки (сортировки данных, слишком больших для размещения в RAM). Данные считываются блоками, каждый блок сортируется в памяти, а блоки сливаются с диска. На этапе слияния из каждого отсортированного фрагмента по одному считывается элемент, поэтому одновременно в памяти хранится только O(k) элементов — по одному на фрагмент. Именно поэтому сортировка слиянием используется в базах данных, Hadoop MapReduce и классических алгоритмах сортировки на магнитной ленте.
# Simulated external sort: sort in chunks then merge
def external_sort(data, chunk_size):
chunks = []
for i in range(0, len(data), chunk_size):
chunk = sorted(data[i:i+chunk_size]) # sort in-memory
chunks.append(chunk)
print(f'Created {len(chunks)} sorted chunks')
# Merge all chunks
import heapq
heap = [(c[0], i, 0) for i, c in enumerate(chunks) if c]
heapq.heapify(heap)
result = []
while heap:
val, ci, ei = heapq.heappop(heap)
result.append(val)
if ei + 1 < len(chunks[ci]):
heapq.heappush(heap, (chunks[ci][ei+1], ci, ei+1))
return result
print(external_sort(list(range(20,0,-1)), 5)[:10])Итоги сортировки слиянием и советы для собеседования
На собеседованиях аккуратная реализация сортировки слиянием демонстрирует понимание рекурсии, шага слияния и стратегии «разделяй и властвуй». Частые дополнительные вопросы:
- Почему O(n log n), а не O(n²)? (уровней log n × работы n на каждом уровне)
- Является ли она стабильной? (Да, используйте <= при слиянии)
- Сколько памяти требуется? (Вспомогательная память O(n) + стек O(log n))
- Можно ли реализовать её итеративно? (Да, с помощью восходящей сортировки слиянием)
- Как применить её к связанному списку? (Проще, чем к массиву: нет затрат O(n) на срез; используйте два указателя — медленный и быстрый, чтобы найти середину)
# One-shot merge sort for interview clarity:
def ms(a):
if len(a) <= 1: return a
m = len(a) // 2
l, r, res, i, j = ms(a[:m]), ms(a[m:]), [], 0, 0
while i < len(l) and j < len(r):
if l[i] <= r[j]: res.append(l[i]); i+=1
else: res.append(r[j]); j+=1
return res + l[i:] + r[j:]
print(ms([5,2,4,6,1,3])) # [1,2,3,4,5,6]Быстрая проверка
Проверьте своё понимание концепций структур данных и алгоритмов — подготовки к собеседованию по программированию, рассмотренных в этом уроке.
Итоги урока
В этом уроке Вы узнали, что сортировка слиянием делит массив в середине, рекурсивно сортирует каждую половину и сливает две отсортированные половины за O(n), получая общее время O(n log n) на протяжении log n уровней рекурсии, на этапе слияния используется <= для выбора левого элемента при равенстве, что гарантирует стабильность, а также что сортировка слиянием является предпочтительным алгоритмом для связанных списков, внешней сортировки и случаев, когда требуется стабильность, тогда как быстрая сортировка предпочтительнее для массивов в памяти при ограниченном объёме памяти. Далее мы реализуем быструю сортировку и изучим стратегии выбора опорного элемента.
Часто задаваемые вопросы
Урок «Сортировка слиянием: разделить, отсортировать, объединить» бесплатный?
Да — полный текст урока «Сортировка слиянием: разделить, отсортировать, объединить» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Сортировка слиянием: разделить, отсортировать, объединить»?
Реализуйте сортировку слиянием рекурсивно, проследите за деревом «разделяй и властвуй» и объясните, почему она гарантирует O(n log n) во всех случаях Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать DSA Interview Prep?
Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «Сортировка слиянием: разделить, отсортировать, объединить»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке DSA Interview Prep?
Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Сортировка пузырьком и сортировка вставками
- Сортировка слиянием: разделить, отсортировать, объединить
- Быстрая сортировка и выбор опорного элемента
- Сортировки без сравнений и sort() в Python