Сортировка – это фундаментальная операция в информатике, которая упорядочивает элементы в определенном порядке. Сортировка слиянием — это эффективный алгоритм сортировки на основе сравнения, известный своей стабильностью и гарантированной временной сложностью в наихудшем случае O(n log n). В этой статье мы рассмотрим различные методы реализации сортировки слиянием в C++ специально для векторов. Мы предоставим примеры кода и обсудим детали их реализации.

Методы сортировки векторов с использованием сортировки слиянием:

Метод 1: рекурсивный подход
Рекурсивная реализация сортировки слиянием делит вектор на более мелкие подвекторы до тех пор, пока каждый подвектор не будет содержать только один элемент. Затем эти подвектора объединяются в отсортированном виде.

#include <iostream>
#include <vector>
void merge(std::vector<int>& vec, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    std::vector<int> leftVec(n1), rightVec(n2);
    for (int i = 0; i < n1; ++i)
        leftVec[i] = vec[left + i];
    for (int j = 0; j < n2; ++j)
        rightVec[j] = vec[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftVec[i] <= rightVec[j])
            vec[k++] = leftVec[i++];
        else
            vec[k++] = rightVec[j++];
    }
    while (i < n1)
        vec[k++] = leftVec[i++];
    while (j < n2)
        vec[k++] = rightVec[j++];
}
void mergeSort(std::vector<int>& vec, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(vec, left, mid);
        mergeSort(vec, mid + 1, right);
        merge(vec, left, mid, right);
    }
}
void printVector(const std::vector<int>& vec) {
    for (const auto& num : vec)
        std::cout << num << " ";
    std::cout << std::endl;
}
int main() {
    std::vector<int> numbers = { 12, 11, 13, 5, 6, 7 };
    mergeSort(numbers, 0, numbers.size() - 1);
    printVector(numbers);
    return 0;
}

Метод 2: итеративный подход
Итеративная реализация сортировки слиянием позволяет избежать рекурсии и использует восходящий подход. Он начинается с субвекторов размером 1 и последовательно объединяет соседние субвекторы, пока не будет отсортирован весь вектор.

#include <iostream>
#include <vector>
void merge(std::vector<int>& vec, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    std::vector<int> leftVec(n1), rightVec(n2);
    for (int i = 0; i < n1; ++i)
        leftVec[i] = vec[left + i];
    for (int j = 0; j < n2; ++j)
        rightVec[j] = vec[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (leftVec[i] <= rightVec[j])
            vec[k++] = leftVec[i++];
        else
            vec[k++] = rightVec[j++];
    }
    while (i < n1)
        vec[k++] = leftVec[i++];
    while (j < n2)
        vec[k++] = rightVec[j++];
}
void mergeSort(std::vector<int>& vec) {
    int size = vec.size();
    int width;
    for (width = 1; width < size; width = 2 * width) {
        for (int left = 0; left < size - 1; left += 2 * width) {
            int mid = left + width - 1;
            int right = std::min(left + 2 * width - 1, size - 1);
            merge(vec, left, mid, right);
        }
    }
}
void printVector(const std::vector<int>& vec) {
    for (const auto& num : vec)
        std::cout << num << " ";
    std::cout << std::endl;
}
int main() {
    std::vector<int> numbers = { 12, 11, 13, 5, 6, 7 };
    mergeSort(numbers);
    printVector(numbers);
    return 0;
}

В этой статье мы рассмотрели два метода реализации сортировки слиянием в C++ специально для векторов: рекурсивный подход и итеративный подход. Рекурсивный подход обеспечивает четкую и интуитивно понятную реализацию сортировки слиянием, тогда как итеративный подход устраняет необходимость в рекурсии и использует стратегию «снизу вверх». Оба метода достигают одной и той же цели — эффективной сортировки векторов.

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

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