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

Также упоминается как: Естественное двухпутевое слияние

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

Естественное слияние работает "снизу вверх" (bottom-up), не используя рекурсию. Мы проходим по массиву и объединяем смежные отсортированные серии.

• Шаг 1. Сканируем массив слева направо и определяем границы первой отсортированной серии (от элемента, где массив перестает возрастать).
• Шаг 2. Сканируем дальше, определяя вторую серию.
• Шаг 3. Вызываем процедуру Merge() (ту самую, из предыдущего урока) для слияния этих двух серий в одну длинную.
• Шаг 4. Продолжаем процесс до конца массива. Если мы дошли до конца и сделали более одной склейки, начинаем проход по массиву заново.
• Конец: Если за весь проход от начала до конца мы нашли только одну серию - массив отсортирован!

Интерактивная модель демонстрирует суть естественного слияния: алгоритм ищет в массиве уже готовые упорядоченные серии и объединяет их.

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

Прелесть этого алгоритма в его адаптивности. Если подать на вход уже отсортированный массив, алгоритм за один проход определит, что серия всего одна, и завершит работу за время O(N). Классический Merge Sort все равно бы потратил O(N log N).

В худшем случае (массив отсортирован по убыванию) алгоритм будет находить серии длиной в 1 элемент и, по сути, сведется к классической восходящей сортировке слиянием. Время работы будет O(N log N).

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

// Функция возвращает индекс конца текущей серии
int GetNextRun(int arr[], int n, int start) {
  int i = start;
  while (i < n - 1 && arr[i] <= arr[i + 1]) {
    i++;
  }
  return i;
}

// Процедура слияния (Merge) аналогична классической
// void Merge(int arr[], int left, int mid, int right) { ... }

void NaturalMergeSort(int arr[], int n) {
  int num_runs = 0;
  
  // Пока не останется всего одна серия на весь массив
  do {
    num_runs = 0;
    int i = 0;
    
    while (i < n) {
      // Находим первую серию
      int end1 = GetNextRun(arr, n, i);
      num_runs++;
      
      // Если первая серия дошла до конца массива - выходим
      if (end1 == n - 1) break;
      
      // Находим вторую серию
      int end2 = GetNextRun(arr, n, end1 + 1);
      
      // Сливаем их
      Merge(arr, i, end1, end2);
      num_runs++; // Считаем получившуюся общую серию
      
      i = end2 + 1; // Сдвигаем указатель для следующих пар
    }
    
  } while (num_runs > 1);
}