C Academy · Урок

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

Q: Урок «Сортировка слиянием» бесплатный?

Да — полный текст урока «Сортировка слиянием» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C Academy, подпишись на CoddyKit PRO. Курс C Academy содержит 4 уроков всего.

Q: Чему я научусь в уроке «Сортировка слиянием»?

Стабильная сортировка Ты практикуешь C Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Q: Нужен ли мне опыт, чтобы начать C Academy?

Предыдущий опыт не требуется. C Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Q: Сколько времени занимает урок «Сортировка слиянием»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Q: Можно ли писать и запускать код в этом уроке C Academy?

Да. Каждый урок C Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Стабильная сортировка

«Сортировка слиянием» — бесплатный урок C Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C Academy содержит 4 уроков всего.

Стабильная сортировка

Сортировка слиянием — это алгоритм сортировки по принципу «разделяй и властвуй»: он делит массив пополам, сортирует каждую половину, а затем снова сливает их. Во всех случаях его сложность равна O(n log n), и он стабилен.

Шаг разделения

Рекурсивно делите массив в середине, пока в каждой части не останется по одному элементу. Один элемент тривиально отсортирован — это базовый случай.

Шаг слияния

Основная операция — слияние двух уже отсортированных последовательностей в одну. Перемещайтесь по обеим с помощью указателей-индексов и каждый раз копируйте следующим меньший первый элемент.

#include <stdio.h>

void merge(int a[], int lo, int mid, int hi, int tmp[]) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi)
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi)  tmp[k++] = a[j++];
    for (int t = lo; t <= hi; t++) a[t] = tmp[t];
}

int main(void) {
    int a[] = {1, 4, 6, 2, 3, 5}; /* two sorted runs */
    int tmp[6];
    merge(a, 0, 2, 5, tmp);
    for (int i = 0; i < 6; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Почему сортировка стабильна

При слиянии используется a[i] <= a[j], поэтому при равенстве двух элементов сначала выбирается элемент из левой последовательности. Поскольку в левой последовательности находились элементы, стоявшие раньше, исходный порядок сохраняется.

Рекурсивный управляющий код

Сортировка слиянием рекурсивно обрабатывает каждую половину, а затем сливает их. Мы передаём общий временный буфер, чтобы не выделять память при каждом вызове.

#include <stdio.h>

void merge(int a[], int lo, int mid, int hi, int tmp[]) {
    int i=lo, j=mid+1, k=lo;
    while (i<=mid && j<=hi) tmp[k++] = (a[i]<=a[j]) ? a[i++] : a[j++];
    while (i<=mid) tmp[k++]=a[i++];
    while (j<=hi)  tmp[k++]=a[j++];
    for (int t=lo;t<=hi;t++) a[t]=tmp[t];
}
void msort(int a[], int lo, int hi, int tmp[]) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    msort(a, lo, mid, tmp);
    msort(a, mid + 1, hi, tmp);
    merge(a, lo, mid, hi, tmp);
}

int main(void) {
    int a[] = {5, 2, 9, 1, 3, 8, 4};
    int tmp[7];
    msort(a, 0, 6, tmp);
    for (int i = 0; i < 7; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Использование памяти

В отличие от быстрой сортировки, сортировке слиянием требуется дополнительная память O(n) для буфера слияния. Это её главный недостаток при работе с очень большими массивами в условиях ограниченной памяти.

Гарантированная сложность O(n log n)

Рекурсия всегда делит массив пополам, поэтому образуется log n уровней, а на каждом уровне сливаются n элементов. Таким образом, сложность сортировки слиянием равна O(n log n) в лучшем, среднем и худшем случаях, в отличие от быстрой сортировки.

Подсчёт уровней слияния

Количество уровней рекурсии равно ceil(log2 n). Вычислим его для нескольких размеров.

#include <stdio.h>

int levels(int n) {
    int L = 0;
    while (n > 1) { n = (n + 1) / 2; L++; }
    return L;
}

int main(void) {
    int sizes[] = {1, 2, 8, 100, 1000};
    for (int i = 0; i < 5; i++)
        printf("n=%d levels=%d\n", sizes[i], levels(sizes[i]));
    return 0;
}

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

Итеративный вариант сливает последовательности размера 1, затем 2, затем 4, удваивая размер на каждом проходе. Он полностью избегает рекурсии и хорошо подходит для связанных списков.

#include <stdio.h>

void merge(int a[], int lo, int mid, int hi, int tmp[]) {
    int i=lo,j=mid+1,k=lo;
    while(i<=mid&&j<=hi) tmp[k++]=(a[i]<=a[j])?a[i++]:a[j++];
    while(i<=mid) tmp[k++]=a[i++];
    while(j<=hi) tmp[k++]=a[j++];
    for(int t=lo;t<=hi;t++) a[t]=tmp[t];
}

int main(void) {
    int a[] = {5, 2, 9, 1, 3, 8}, n = 6, tmp[6];
    for (int width = 1; width < n; width *= 2)
        for (int lo = 0; lo < n - width; lo += 2 * width) {
            int mid = lo + width - 1;
            int hi = (lo + 2*width - 1 < n-1) ? lo + 2*width - 1 : n-1;
            merge(a, lo, mid, hi, tmp);
        }
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Когда выбирать сортировку слиянием

Выбирайте сортировку слиянием, если Вам нужны:

гарантированная сложность O(n log n) без неблагоприятных случаев
стабильность
сортировка связанных списков (произвольный доступ не требуется)
внешняя сортировка данных, слишком больших для RAM