Алгоритм сортировки слиянием (Merge Sort): принцип работы

Также упоминается как: Метод слияния, Простое двухпоточное слияние, Прямое слияние

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

Процесс сортировки слиянием можно разбить на два главных шага:

• Разделение (Divide): Массив рекурсивно разбивается ровно пополам до тех пор, пока каждый подмассив не станет длиной в 1 элемент (массив из 1 элемента по определению отсортирован).
• Слияние (Merge): Берем два соседних отсортированных подмассива и объединяем их в один больший отсортированный. Для этого нам нужен дополнительный буферный массив такого же размера. Мы сравниваем первые элементы двух подмассивов и берем наименьший из них, сдвигая указатель.

В тренажере показана работа сортировки слиянием: массив дробится пополам, а затем отсортированные половинки аккуратно склеиваются.

Анализ сложности

В отличие от сортировки Хоара, у сортировки слиянием нет худшего случая в плане времени работы. Она всегда стабильно делит массив пополам и тратит ровно линейное время на слияние на каждом уровне. Глубина дерева рекурсии равна log₂N. Итоговая временная сложность строго равна O(N log N).

Однако за эту стабильность приходится платить оперативной памятью: алгоритму обязательно требуется дополнительный массив размером N для проведения слияния, что дает пространственную сложность O(N). Из-за этого классическую сортировку слиянием редко используют для сортировки примитивных типов в оперативной памяти (предпочитая алгоритмы сортировки "на месте", такие как сортировка Хоара или пирамидальная сортировка).

Зато сортировка слиянием идеально подходит для сортировки связных списков (где слияние можно делать перекидыванием указателей без дополнительной памяти) и для внешней сортировки (сортировки огромных файлов на диске).

Реализация на C

// Вспомогательная функция слияния двух отсортированных частей
void Merge(int arr[], int left, int mid, int right) {
  int i = left, j = mid + 1, k = 0;
  // Динамически выделяем временный массив
  int *temp = (int *)malloc((right - left + 1) * sizeof(int));

  // Сравниваем элементы и сливаем в temp
  while (i <= mid && j <= right) {
    if (arr[i] <= arr[j]) {
      temp[k++] = arr[i++];
    } else {
      temp[k++] = arr[j++];
    }
  }

  // Дописываем оставшиеся элементы из левой части
  while (i <= mid) temp[k++] = arr[i++];
  
  // Дописываем оставшиеся элементы из правой части
  while (j <= right) temp[k++] = arr[j++];

  // Копируем результат обратно в оригинальный массив
  for (i = left, k = 0; i <= right; i++, k++) {
    arr[i] = temp[k];
  }
  
  free(temp); // Обязательно освобождаем память!
}

// Основная рекурсивная функция
void MergeSort(int arr[], int left, int right) {
  if (left < right) {
    int mid = left + (right - left) / 2;

    // Рекурсивно сортируем левую и правую половины
    MergeSort(arr, left, mid);
    MergeSort(arr, mid + 1, right);

    // Сливаем две отсортированные половины
    Merge(arr, left, mid, right);
  }
}