Визуализация
Данные: Случайные
Легенда цветов
Как работает сортировка слиянием
Идея алгоритма. Массив рекурсивно делится пополам до тех пор, пока не останутся подмассивы из одного элемента. Затем соседние подмассивы сливаются в один, причем при слиянии элементы сразу расставляются в правильном порядке. В итоге за log n уровней рекурсии весь массив оказывается отсортированным.
Фаза разделения. На каждом шаге массив делится ровно пополам (по индексу mid = (lo + hi) / 2). Деление продолжается рекурсивно, пока участок не сожмется до одного элемента. Один элемент - это уже отсортированный массив.
Фаза слияния. Два отсортированных участка сливаются в один: берем по указателю из каждой половины, сравниваем, меньший элемент копируем в результат. Когда одна половина заканчивается, остаток другой дописывается без сравнений.
Почему нужна дополнительная память. В отличие от пузырьковой или быстрой сортировки, merge sort не может работать "на месте" без вспомогательного массива. При слиянии нужно куда-то копировать элементы, прежде чем записать результат обратно. Поэтому дополнительная память - O(n).
- Случайные - типичный средний случай, всегда n log n операций.
- В обратном порядке - столько же сравнений, что и на случайных данных.
- Отсортированные - сравнений ровно столько же: алгоритм не проверяет, отсортирован ли массив заранее.
- Почти отсортированные - количество операций практически не меняется.
- Одинаковые - сравнения идут, но всегда берется элемент из левой половины (устойчивость).
Синонимы названия. Этот алгоритм также известен как сортировка слиянием (основное русское название), merge sort (английское название) и сортировка объединением.
Сложность алгоритма
Сложность - это оценка того, как быстро растет потребление ресурса при росте длины массива n. Ресурса у алгоритма два, поэтому и оценки две: по времени и по памяти. Обе записывают через O-нотацию - у нас есть отдельная анимация о том, как читать такие записи.
По времени
Показывает, как растет число операций (здесь это сравнения и копирования) при росте n. Лейбл "Сложность" под визуализацией - время, которое получилось фактически на ваших данных.
| Случай | Время | Комментарий |
|---|---|---|
| Лучший | O(n log n) | Даже на отсортированных данных алгоритм делит и сливает |
| Средний | O(n log n) | Число сравнений стабильно: всегда log n уровней рекурсии |
| Худший | O(n log n) | Гарантированная верхняя граница, без вырождений |
По памяти
Показывает, сколько дополнительной памяти нужно алгоритму. Сам входной массив в эту оценку не входит: дополнительной считается память сверх него.
| Характеристика | Оценка | Комментарий |
|---|---|---|
| Дополнительная память | O(n) | Нужен вспомогательный массив для слияния. Это главный недостаток по сравнению с сортировками на месте |
Устойчивость алгоритма
Устойчивой называется сортировка, которая не меняет взаимный порядок равных элементов. Пример: сортируем учеников по оценке, а внутри одной оценки они уже стояли по алфавиту. Устойчивая сортировка сохранит алфавитный порядок внутри каждой оценки, неустойчивая - может перемешать.
| Характеристика | Оценка | Комментарий |
|---|---|---|
| Устойчивость | Да | При слиянии равных элементов берем из левой половины первым: исходный порядок сохраняется. Проверьте на наборе "Одинаковые" |
Примеры реализации сортировки слиянием (Merge Sort)
Код на C
// Слияние двух отсортированных половин массива
void merge(int arr[], int lo, int mid, int hi) {
int n1 = mid - lo + 1;
int n2 = hi - mid;
int left[n1], right[n2];
// Копируем данные во временные массивы
for (int i = 0; i < n1; i++) left[i] = arr[lo + i];
for (int j = 0; j < n2; j++) right[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = lo;
// Сливаем, выбирая меньший элемент
while (i < n1 && j < n2) {
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
// Дописываем остатки
while (i < n1) { arr[k] = left[i]; i++; k++; }
while (j < n2) { arr[k] = right[j]; j++; k++; }
}
// Рекурсивная сортировка слиянием
void merge_sort(int arr[], int lo, int hi) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
merge_sort(arr, lo, mid);
merge_sort(arr, mid + 1, hi);
merge(arr, lo, mid, hi);
}Код на Python
def merge_sort(arr):
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, 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Код на JavaScript
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]);
i++;
} else {
result.push(right[j]);
j++;
}
}
// Дописываем остатки
while (i < left.length) { result.push(left[i]); i++; }
while (j < right.length) { result.push(right[j]); j++; }
return result;
}Хотите разобрать тему глубже? В нашем бесплатном курсе есть урок про сортировку слиянием - с подробной теорией, задачами и проверочными вопросами.