Wave Merge Sort — новий алгоритм сортування

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті.

Вітаю, мене звати Ярослав, я .NET розробник, працював довгий час в продуктовій компанії на посаді Back-End Developer, а згодом і Architect.

Хочу поділитись власною розробкою нового алгоритму сортування. З одного боку, він виглядає як покращення класичного алгоритму Merge Sort, але загалом тут використаний зовсім інший підхід, ба навіть сам метод злиття змінений. Але давайте по порядку.

Вивчивши багато різних алгоритмів сортування, я зупинився на аналізі саме алгоритму Merge Sort так як він є стабільним і швидким, що дозволяє використовувати його для сортування великих об’ємів даних.

Стабільним є алгоритм, що підтримує відносний порядок елементів із однаковими ключами сортування.

Малюнок 1. Сортуючи по значенню Grade, ми не втрачаємо порядок елементів з однаковими значеннями. Це і є стабільність алгоритму сортування.

Merge Sort використовує рекурсивний підхід поділом масиву навпіл і злиттям уже відсортованих підмасивів. Але він не аналізує дані, тому кількість операцій порівняння та заміни є суттєвою навіть для вже відсортованого масиву. А ще рекурсія на гігантських об’ємах даних може закінчитись всім знайомим і неприємним Stack Overflow.

Алгоритм

Я вирішив зайнятись цією проблемою і на базі багатьох аналізів і напрацювань вийшов наступний алгоритм:

1. Проходячи по масиву ми будемо стикатись або з ростом значень (чи однаковими значеннями), або зі спаданням. Я назвав ці діапазони хвилями, бо у хвилі також є сторона підйому і сторона спаду.
2. Спадні хвилі ми перевертаємо (reverse), отримуючи хвилі росту. Таким чином, у нас після проходу всього масиву будуть тільки хвилі росту або ж рівні хвилі, якщо їх ключі сортування однакові. Маленькі хвилі на льоту зливаються за допомогою insertion sort, щоби зменшити їх загальну кількість.
3. Зберігаючи індекси кінців хвиль, ми будемо мати вже готовий набір відсортованих підмасивів для фінального злиття.
4. Ну і врешті-решт, відсортовані підмасиви зливаються і заданий масив є відсортованим.

Приклад

Ми маємо на вході наступний масив:

На малюнку нижче зображені описані вище кроки алгоритму:

Малюнок 2. Візуальні кроки алгоритму Wave Merge Sort.

Код

Наведу код основного методу, де відбувається знаходження всіх хвиль і їх злиття. Намагався за допомогою коментарів у коді все пояснити. Повний код можна подивитись на сторінці алгоритму у GitHub.

public void Sort(int[] arr, int left, int right)

{

    int n = right - left + 1;

    if (n < 2)

        return;

    // init the array to store ending indices of waves

    int[] waves = new int[n / 3 + 2];

    // init waves counter

    int w = 0;

    // init a wave start index

    int l = left;

    // init a previous wave start index

    int p = left;

    // prepare waves for merging

    int i = left + 1;

    while (i <= right)

    {

        if (arr[i - 1] > arr[i])

        {

            // go down the wave

            while (i < right && arr[i] > arr[i + 1])

            {

                i++;

            }

            // reverse the current descent wave

            reverse(arr, l, i);

        }

        // climb up the wave

        while (i < right && arr[i] <= arr[i + 1])

        {

            i++;

        }

        // Try to merge last two small waves in place to reduce the number of waves.

        // The "6" is optimal number of elements to merge in place.

        if (w > 0 && i - p < 6)

        {

            mergeInPlace(arr, p, l, i);

            w--;

        }

        else

        {

            p = l;

        }

        if (i < right)

        {

            // add a new wave's index

            waves[w++] = i;

            // set the next wave start

            l = ++i;

        }

        i++;

    }

    // merge the prepared waves

    for (int step = 1; step <= w; step = 2 * step)

    {

        // the starting index of the first wave

        l = left;

        for (i = step - 1; i < w; i += 2 * step)

        {

            // the ending index of the first wave

            int m = waves[i];

            // the index of the second wave

            p = i + step;

            // calculate the ending index of the second wave

            p = p < w ? waves[p] : right;

            // merge two waves

            merge(arr, l, m, p);

            // set the start of the next wave

            l = p + 1;

        }

    }

}

Чи є Wave Merge Sort стабільним?

Так, цей алгоритм є стабільним.

Часова складність

Best Case: O(n)

Average Case: O(n log n)

Worst Case: O(n log n)

Допоміжний простір

O(4n / 3 + 2) — Алгоритм використовує допоміжні масиви для злиття та збереження індексів хвиль.

Переваги

• Швидке сортування вже відсортованих (байдуже чи в порядку зростання, чи спадання) масивів або якщо масив має досить значні такі діапазони
• Відсутність рекурсії
• Мінімальна кількість операцій порівняння і заміни у порівнянні з класичним Merge Sort

Недоліки

• Виділення допоміжних масивів для злиття та збереження індексів хвиль

Benchmarks

Настав час порівняти результати роботи алгоритмів Merge Sort і Wave Merge Sort. Я покажу середній час роботи для різних масивів по розміру і розподілу елементів. Середній час взято з 20 прогонів кожного виду.

Малюнок 3. Порівняльна статистика роботи алгоритмів Wave Merge Sort та Merge Sort.

Як видно з результатів, алгоритм показав свою ефективність і виграш у порівнянні з класичним Merge Sort.

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