CodeUtility
Кодить проще - жить легче!
Алгоритмы C/C++

Сортировка слиянием (merge sort) в C и C++

В этом уроке вы реализуете сортировку слиянием по стратегии «разделяй и властвуй», которая всегда работает за O(n log n).

Введение

Сортировка слиянием делит массив на две половины, сортирует каждую рекурсивным вызовом и сливает две отсортированные половины в одну упорядоченную последовательность. Её главное преимущество - стабильное время работы O(n log n) независимо от состояния входных данных.

Главное

  • Проверяйте на пустом вводе, одном элементе, повторах и уже отсортированных данных.
  • Сначала добейтесь правильной работы кода, а потом оптимизируйте.
  • В реальном коде отдавайте предпочтение готовым функциям стандартной библиотеки.

Визуализация: Сортировка слиянием (merge sort) в C и C++

O(n)

Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.

Примеры кода на C и C++

C
Запустить →
main.c
#include <stdio.h>
#include <stdlib.h>

void merge_sort(int *values, int *temporary, int left, int right) {
    if (right - left < 2) return;
    int middle = (left + right) / 2;
    merge_sort(values, temporary, left, middle);
    merge_sort(values, temporary, middle, right);

    int first = left;
    int second = middle;
    int output = left;
    while (first < middle && second < right) {
        temporary[output++] = values[first] < values[second]
            ? values[first++] : values[second++];
    }
    while (first < middle) temporary[output++] = values[first++];
    while (second < right) temporary[output++] = values[second++];
    for (int index = left; index < right; ++index) {
        values[index] = temporary[index];
    }
}

int main(void) {
    int values[] = {8, 3, 6, 2, 7};
    int temporary[5];
    merge_sort(values, temporary, 0, 5);
    for (int index = 0; index < 5; ++index) {
        printf("%d ", values[index]);
    }
}
Результат выполнения
2 3 6 7 8
C++
Запустить →
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>

void merge_sort(std::vector<int>& values) {
    if (values.size() < 2) return;
    auto middle = values.begin() + values.size() / 2;
    std::vector<int> left(values.begin(), middle);
    std::vector<int> right(middle, values.end());
    merge_sort(left);
    merge_sort(right);
    std::merge(left.begin(), left.end(), right.begin(), right.end(),
               values.begin());
}

int main() {
    std::vector values{8, 3, 6, 2, 7};
    merge_sort(values);
    for (int value : values) {
        std::cout << value << ' ';
    }
}
Результат выполнения
2 3 6 7 8

Сравнение C и C++

Функция merge_sort на C останавливается, когда в участке меньше 2 элементов. После сортировки обеих половин цикл while каждый раз выбирает меньший из двух первых элементов и копирует его во временный массив temporary, а затем копирует остаток. Обеим версиям нужно O(n) дополнительной памяти. Версия на C сама управляет временным массивом, а версия на C++ использует vector и стандартные алгоритмы, чтобы код был понятнее.

C

Циклы, указатели, длины и временные буферы пишутся явно.

C++

Итераторы и стандартные алгоритмы отделяют обработку от способа хранения данных.

Упражнения для практики

Запустите обе версии, а затем измените код, чтобы увидеть разницу в безопасности, которую даёт каждый язык.

  • Пройдите каждое сравнение на бумаге.
  • Проверьте на повторах и на очень больших и очень маленьких значениях.
  • Измерьте время работы своего кода и сравните его со стандартной библиотекой.

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи