Участник:KulikovM

Свойства и структура алгоритма

Общее описание

Сортировка слиянием упорядочивает набор элементов вида Aᵢ (1 ≤ i ≤ n) путём рекурсивного деления набора на две части и последующего слияния отсортированных половин. В последовательно-параллельном варианте две рекурсивные ветви (левая и правая) выполняются параллельно, а операция merge в каждом узле выполняется последовательно.

Математическое описание

Пусть n ≥ 2. Набор элементов Aᵢ делится на две части:

• левая часть: элементы Aᵢ, где 1 ≤ i ≤ ⌊n/2⌋
• правая часть: элементы Aⱼ, где ⌊n/2⌋ + 1 ≤ j ≤ n

Затем рекурсивно сортируются обе части и выполняется операция слияния.

Базовый случай:

• если n = 1, набор считается уже отсортированным.

Операция слияния (merge)

Операция merge объединяет два упорядоченных диапазона элементов в один общий отсортированный набор.

В процессе слияния используются три индекса:

• i — пробегает левую часть, 1 ≤ i ≤ ⌊n/2⌋
• j — пробегает правую часть, ⌊n/2⌋ + 1 ≤ j ≤ n
• k — позиция результирующего набора, 1 ≤ k ≤ n

Алгоритм слияния (по умолчанию — неубывание):

1. сравниваются элементы Aᵢ и Aⱼ;
2. меньший из них записывается в Aₖ;
3. затем увеличивается индекс (i или j) и индекс k;
4. когда один диапазон завершается, оставшиеся элементы второго дописываются в конец результирующего набора.

• Невозрастание: в шагах сравнения выше используйте знак ≥ вместо ≤ (то есть выбирайте больший элемент).
• Стабильность: при равенстве значений сначала берите элемент из левой части — это сохраняет порядок равных элементов.

Вычислительное ядро

Вычислительное ядро алгоритма состоит из последовательных слияний на каждом шаге рекурсии, в которых поочерёдно сравниваются элементы Aᵢ и Aⱼ и формируется результирующая упорядоченная последовательность в позиции Aₖ. Для невозрастания меняется только знак в сравнении (≥ вместо ≤).

Макроструктура

Макроструктурно алгоритм представляется в виде бинарного дерева рекурсивных вызовов:

• на каждом уровне дерево делит исходный набор элементов на две части,
• каждая ветвь обрабатывается независимо (возможен параллелизм),
• на обратном ходе рекурсии пары отсортированных фрагментов объединяются посредством слияния.

Таким образом:

• последовательность вычислений на нисходящем этапе — разбиение набора по индексам,
• последовательность вычислений на восходящем этапе — поэлементное слияние через сравнение Aᵢ и Aⱼ с записью результата в Aₖ.

Схема последовательной реализации

В последовательной реализации рекурсивная сортировка левой части выполняется полностью, затем сортируется правая часть, и лишь после этого вызывается операция merge. Для невозрастания меняется только знак сравнения в merge (≥ вместо ≤).

Последовательная сложность

Общая сложность определяется затратами на:

• разбиение на две части (O(1)),
• сортировку левой части O((n/2) log(n/2)),
• сортировку правой части O((n/2) log(n/2)),
• слияние (линейный проход: k от 1 до n ⇒ O(n)).

Итого: T(n) = O(n log n) по времени и O(n) дополнительная память под результирующую перестановку.

Информационный граф

Информационный граф представляет собой дерево:

Информационный граф сортировки слиянием (n=8)

Ресурс параллелизма

Параллелизм достигается за счёт независимой обработки двух половин набора. На уровне слияния параллелизм отсутствует (последовательное сравнение Aᵢ и Aⱼ → Aₖ). Высота параллельной части определяется глубиной рекурсии: O(log n).

Вход/выход

1. Вход: массив A из n сравнимых элементов.
2. Выход: тот же массив, отсортированный по неубыванию (по умолчанию) либо по невозрастанию (если в merge поменять ≤ на ≥).

Свойства

• Стабильный алгоритм (равные элементы сохраняют порядок при выборе элемента из левой части при равенстве).
• Хорошо подходит для больших массивов.
• Естественно поддерживает распараллеливание рекурсивной части.

Программная реализация алгоритма

Последовательная реализация (псевдокод)

procedure MergeSort(A, l, r):
    if r - l + 1 <= 1: return
    m := (l + r) // 2
    MergeSort(A, l, m)
    MergeSort(A, m+1, r)
    Merge(A, l, m, r)            // слияние двух отсортированных фрагментов

// Слияние по неубыванию (для невозрастания заменить ≤ на ≥)
procedure Merge(A, l, m, r):
    i := l           // индекс в левой части
    j := m + 1       // индекс в правой части
    k := 0           // индекс во временном буфере B[0 .. r-l]
    B := new array of size (r - l + 1)

    while i ≤ m and j ≤ r:
        if A[i] ≤ A[j]:          // <-- для невозрастания здесь использовать A[i] ≥ A[j]
            B[k] := A[i]; i := i + 1
        else
            B[k] := A[j]; j := j + 1
        k := k + 1

    while i ≤ m:  B[k] := A[i]; i := i + 1; k := k + 1
    while j ≤ r:  B[k] := A[j]; j := j + 1; k := k + 1

    // копирование результата назад
    for t := 0 .. (r - l):
        A[l + t] := B[t]

Параллельная реализация (последовательно-параллельная)

Псевдокод:

procedure PMergeSort(A, l, r):
    if r - l + 1 <= 1: return
    m := (l + r) // 2

    parallel:
        PMergeSort(A, l,   m)     // ветвь 1
        PMergeSort(A, m+1, r)     // ветвь 2
    join

    Merge(A, l, m, r)             // слияние — последовательное

Параллельная реализация

Иерархия параллелизма:

1. Распределение данных между MPI-процессами
2. Независимая локальная сортировка в каждом процессе
3. Рекурсивное слияние внутри локальной сортировки

Оценка сложности:

• Вычисления: O((n/p)log(n/p)) на процесс + O(n) на слияния

• Коммуникации: O(log p) шагов, O(n) общий объем пересылок

• Память: O(n/p) на процесс + временные буферы

MPI код на Си с замерами времени и генерацией данных

#include <stdio.h>
#include <stdlib.h>
#include <mpi.h>

// Функция слияния двух отсортированных массивов
int* merge(int *a, int na, int *b, int nb) {
    int *c = malloc((na + nb) * sizeof(int));
    int i = 0, j = 0, k = 0;
    
    // Слияние двух массивов в один отсортированный
    while (i < na && j < nb) {
        if (a[i] < b[j]) c[k++] = a[i++];
        else c[k++] = b[j++];
    }
    
    // Добиваем остатки из первого массива
    while (i < na) c[k++] = a[i++];
    // Добиваем остатки из второго массива
    while (j < nb) c[k++] = b[j++];
    
    return c;
}

// Рекурсивная сортировка слиянием
int* msort(int *arr, int n) {
    if (n <= 1) {
        int *r = malloc(n * sizeof(int));
        if (n == 1) r[0] = arr[0];
        return r;
    }
    
    // Делим массив пополам
    int mid = n / 2;
    // Сортируем левую часть рекурсивно
    int *left = msort(arr, mid);
    // Сортируем правую часть рекурсивно
    int *right = msort(arr + mid, n - mid);
    // Сливаем отсортированные части
    int *result = merge(left, mid, right, n - mid);
    
    // Освобождаем временные массивы
    free(left);
    free(right);
    return result;
}

int main(int argc, char *argv[]) {
    MPI_Init(&argc, &argv);
    
    int rank, size;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);  // Получаем номер процесса
    MPI_Comm_size(MPI_COMM_WORLD, &size);  // Получаем общее количество процессов
    
    // Проверка аргументов командной строки
    if (argc < 2 && rank == 0) {
        printf("Usage: %s <array_size>\n", argv[0]);
        MPI_Finalize();
        return 1;
    }
    
    int n = atoi(argv[1]);          // Общий размер массива
    int local_n = n / size;         // Размер части на процесс
    int *data = NULL;               // Буфер для всего массива (только в процессе 0)
    int *local = malloc(local_n * sizeof(int));  // Локальная часть массива
    
    int i;
    int step;
    
    // Генерация данных в процессе 0
    if (rank == 0) {
        data = malloc(n * sizeof(int));
        for (i = 0; i < n; i++) {
            data[i] = rand() % 1000000;  // Заполнение случайными числами
        }
    }
    
    double start = MPI_Wtime();  // Замер времени начала
    
    // Распределение данных между процессами (Scatter)
    MPI_Scatter(data, local_n, MPI_INT, local, local_n, MPI_INT, 0, MPI_COMM_WORLD);
    
    if (rank == 0) free(data);  // Освобождаем исходный массив в процессе 0
    
    // Локальная сортировка - каждый процесс сортирует свою часть
    int *sorted_local = msort(local, local_n);
    free(local);
    
    int *result = sorted_local;  // Результирующий массив процесса
    int result_size = local_n;   // Размер результата
    
    // Иерархическое слияние - кооперативная операция между процессами
    for (step = 1; step < size; step *= 2) {
        if (rank % (2 * step) == 0) {
            // Процесс-получатель: получает данные от партнера и сливает
            if (rank + step < size) {
                int partner_size;
                // Получаем размер данных от партнера
                MPI_Recv(&partner_size, 1, MPI_INT, rank + step, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
                
                int *partner_data = malloc(partner_size * sizeof(int));
                // Получаем сами данные от партнера
                MPI_Recv(partner_data, partner_size, MPI_INT, rank + step, 1, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
                
                // Сливаем свой результат с данными партнера
                int *merged = merge(result, result_size, partner_data, partner_size);
                free(result);
                free(partner_data);
                
                result = merged;
                result_size += partner_size;
            }
        } else if (rank % step == 0) {
            // Процесс-отправитель: отправляет свои данные и завершает работу
            MPI_Send(&result_size, 1, MPI_INT, rank - step, 0, MPI_COMM_WORLD);
            MPI_Send(result, result_size, MPI_INT, rank - step, 1, MPI_COMM_WORLD);
            free(result);
            break;  // Завершаем цикл для этого процесса
        }
    }
    
    double end = MPI_Wtime();  // Замер времени окончания
    
    // Вывод результата в процессе 0
    if (rank == 0) {
        printf("Processes: %d, Elements: %d, Time: %.6f seconds\n", size, n, end - start);
        free(result);
    }
    
    MPI_Finalize();
    return 0;
}

Основные MPI операции:

• MPI_Init/MPI_Finalize - инициализация/завершение MPI.

• MPI_Comm_rank/MPI_Comm_size - получение номера процесса и общего числа процессов.

• MPI_Scatter - распределение данных от процесса 0 ко всем процессам.

• MPI_Send/MPI_Recv - передача данных между процессами при слиянии.

Обоснование выбора MPI

MPI был выбран, так как «Ломоносов-2», на котором проводились прогоны, является кластером с распределенной памятью.

Литература и источники

• Н. Вирт. Алгоритмы и структуры данных. § 2.4 «Сортировка последовательностей» (с. 97). PDF (стр. 97)