Алгоритм злиття

Алгоритми злиття - це родина алгоритмів, які використовують декілька відсортованих списків як вхідні дані та створюють єдиний вихідний список, що містить усі елементи списків входів у впорядкованому порядку. Ці алгоритми використовуються як підпрограми в різних алгоритмах сортування, найбільш відомі з них сортування злиттям.

Застосування

Сортування злиттям

Алгоритм злиття відіграє важливу роль в алгоритмі сортування злиттям, алгоритмі сортування на основі порівняння. Концептуально алгоритм сортування злиттям складається з двох етапів:

1. Рекурсивно розділяємо список на підсписки приблизно однакової довжини, до тих пір, доки кожен підсписок буде містити лише один елемент, або у випадку ітеративного (знизу вгору) сортування злиттям розглядається список з n елементів як n підсписків розміром 1(будь-який список довжини 1 можна вважати впорядкованим).
2. Послідовно об’єднуємо підсписки, щоб створити новий впорядкований підсписок - на кожному кроці ми беремо менший з двох перших елементів підсписків і записуємо його в результуючий список. Лічильники номерів елементів результуючого списку і підсписку, з якого було взято елемент, збільшуємо на 1.
3. Коли один з підсписків вичерпався, додаємо всі елементи, що залишилися з другого підсписку в результуючий список.
4. Якщо результуючий список буде містити усі елементи - це впорядкованийй список.

Алгоритм злиття використовується неодноразово в алгоритмі сортування злиттям.

Приклад сортування злиття наведено на ілюстрації. Починається з невпорядкованого масиву з 7 цілих чисел. Масив розділений на 7 частин; кожна частина містить 1 елемент і впорядковується. Потім відсортовані частини об'єднуються для отримання більших, відсортованих частин, поки не залишиться 1, відсортований масив.

Алгоритм був винайдений Джоном фон Нейманом в 1945 році під час роботи над "Манхеттенським проектом" як засіб обробки великих масивів статистичних даних.

Об'єднання двох списків

Об'єднання двох впорядкованих списків в один може бути зроблено в лінійному часу і лінійної або постійного простору (в залежності від моделі доступу до даних). Наведений нижче псевдокод демонструє алгоритм, який реалізує злиття вхідних списків (або пов'язані списки або масиви) А і В у новий список С

head() - дає перший елемент списку;

append - додає елемент до списку;

drop - вилучає перший елемент списку зі збільшенням покажчика або індексу.

algorithm merge(A, B) is
    inputs A, B : list
    returns list

    C := new empty list
    while A is not empty and B is not empty do
        if head(A) ≤ head(B) then
            append head(A) to C
            drop the head of A
        else
            append head(B) to C
            drop the head of B

    // By now, either A or B is empty. It remains to empty the other input list.
    while A is not empty do
        append head(A) to C
        drop the head of A
    while B is not empty do
        append head(B) to C
        drop the head of B

    return C

Підтримка в мовах програмування

Деякі мови програмування мають вбудовані або бібліотечні функції підтримки для об'єднання упорядкованих колекцій.

C ++

Стандартна бібліотека шаблонів С ++ має функцію std::merge, яка об'єднує два упорядковано діапазони ітератори і std:: inplace_merge, який об'єднує два послідовних відсортованих діапазонів в місці. Крім того, std::list (зв'язаний список) клас має свій власний метод об'єднання, який об'єднує ще один список в себе. Тип елементів злиті повинен підтримувати менш ніж оператор (<), або вона повинна бути забезпечена за допомогою призначеного для користувача компаратора.

C ++ 17 дозволяє відрізняючись політики виконання, а саме послідовні, паралельні і паралельно-unsequenced. [9]

Python

Стандартна бібліотека мови Python (з 2.6) також має функцію злиття в модулі heapq, який приймає кілька відсортованих ітеріруемий, і об'єднують їх в єдиний итератор. [10]