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

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

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

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

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

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

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

Робота цих алгоритмів зазвичай займає час, пропорційну сумі довжин списків. Ці алгоритми також працюють з кількома рядками, помноженим на сумарну довжину, час від часу, щоб помістити індекс на найменший елемент, що може бути досягнуто за допомогою порядку пріоритету, який заснований на моменті часу O (log n), O (m log n) time, де n — кількість списків, які потрібно з'єднати, а m — сума довжин списків. Коли два списки довжиною m з'єднуються, нижня межа порівняння в гіршому випадку становить 2m — 1.

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

first() — подає перший елемент списку;

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

rest() — подає список без першого елементу.

function merge(A,B)
    var list C
    while length(A) > 0 and length(B) > 0
        if first(A) ≤ first(B)
            append first(A) to C
            A = rest(A)
        else
            append first(B) to C
            right = rest(B)
        end if
    while length(A) > 0 
        append first(A) to C
        A = rest(A)
    while length(B) > 0 
        append first(B) to C
        B = rest(B)
    return C

Для роботи алгоритму ми повинні реалізувати наступні операції:

• Операцію для рекурсивного поділу масиву на групи (метод Sort).
• Злиття в правильному порядку (метод Merge).

public void Sort(T[] items)
{
    if (items.Length <= 1)
    {
         return;
    }       

    int leftSize = items.Length / 2;
    int rightSize = items.Length - leftSize;
    T[] left = new T[leftSize];
    T[] right = new T[rightSize];
    Array.Copy(items, 0, left, 0, leftSize);
    Array.Copy(items, leftSize, right, 0, rightSize);
    Sort(left);
    Sort(right);
    Merge(items, left, right);
}  

private void Merge(T[] items, T[] left, T[] right)
{
    int leftIndex = 0;
    int rightIndex = 0;
    int targetIndex = 0;
    int remaining = left.Length + right.Length;
    while(remaining > 0)
    {
        if (leftIndex >= left.Length)
        {
            items[targetIndex] = right[rightIndex++];
        }
        else if (rightIndex >= right.Length)
        {
            items[targetIndex] = left[leftIndex++];
        }
        else if (left[leftIndex].CompareTo(right[rightIndex]) < 0)
        {
            items[targetIndex] = left[leftIndex++];
        }
        else
        {
            items[targetIndex] = right[rightIndex++];
        }
 
        targetIndex++;
        remaining--;
    }
}

Варто відзначити, що на відміну від лінійних алгоритмів сортування, сортування злиттям буде ділити і склеювати масив незалежно від того, був він відсортований спочатку чи ні. Тому, незважаючи на те, що в гіршому випадку він відпрацює швидше, ніж лінійний, в кращому випадку його продуктивність буде нижче, ніж у лінійного. Тому сортування злиттям — не найкраще рішення, коли треба впорядкувати частково впорядкований масив.

У мультипрограмуванні масиви відсортованих значень можна ефективно об'єднати, використовуючи задачу пошуку всіх найближчих найменших значень.

Паралельне злиття також може бути реалізоване за допомогою алгоритму поділу за правилом. Цей алгоритм добре працює, коли використовується з швидким послідовним злиттям як базовий випадок для об'єднання малих масивів. Реалізація з використанням Intel Threading Building Blocks (TBB) та бібліотеки паралельних шаблонів Microsoft (PPL), яка працює з багатоядерними процесорами, добре зарекомендувала себе на практиці[4].

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

• Алгоритм сортування
• Сортування злиттям

• Donald Knuth . The Art of Computer Programming , Volume 3: Sorting and Searching , Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0 . Pages 158—160 of section 5.2.4: Sorting by Merging. Section 5.3.2: Minimum-Comparison Merging, pp.  197—207.
• Thimas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1
• High Performance Implementation of Parallel and Serial Merge in C# with source in GitHub and in C++ GitHub
• Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2009). «Section 27.3: Multithreaded merge sort». Introduction to Algorithms (Third изд.). MIT Press and McGraw-Hill. стр. 797—804. ISBN 978-0-262-03384-8.