Сортування злиттям: алгоритм, переваги і особливості

Кучер В.Г.

Реалізація першого етапу

Рекурсивне розбиття масиву показано нижче.

void mergeSort(T a[], long start, long finish) {
long split;
if (start < finish) {
split = (start + finish)/2;
mergeSort(a, start, split);
mergeSort(a, split+1, finish);
merge(a, start, split, finish);
}
}

Що відбувається в цьому коді:

  • Функція mergeSort отримує вихідний масив a і ліву і праву границі ділянки, який необхідно відсортувати (індекси start і finish).
  • Якщо довжина цієї ділянки більше одиниці (start < finish), то він розбивається на дві частини (за індексом split), і кожна з них рекурсивно сортується.
  • У рекурсивний виклик функції лівого боку передається початковий індекс ділянки та індекс split. Для правої, відповідно, початком (split + 1), а кінцем – останній індекс вихідного ділянки.
  • Функція merge отримує дві впорядковані послідовності (a[start]…a[split] і a[split+1]…a[finish]) і зливає їх із збереженням порядку сортування.
    • Цікаве:  Золото ртуті: метод отримання, застосування ртуті в сучасній промисловості

    Механіка роботи функції merge розглянута вище.

    Сторінка: 1 2 3 4 5 6 7 8 9 10