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.

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

👍ПодобаєтьсяСподобалось10
До обраногоВ обраному1
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Я б детальніше розглянув масиви де одна з хвиль дуже довга. Наприклад- перша половина відсортована, інша — 01010... Для mergesort не обов’язково використовувати пам’ять стеку якщо StackOverflow може бути проблемою

Не зовсім зрозумів вас, другу половину прийдеться сортувати і потім мержити з першою в будь-якому разі.
І мерж буде юзати пам’ять додаткову, як без цього?

Афтар, ми тобi вiрили як самому собi. Пообiцяв нам 14% прирiст швидкодii.
А ти .. нас обманув, реальнiсть трохи прозаiчнiша.

var arr = new int[20000];

            var rand = new Random();

            for (int i = 0; i < arr.Length; i++)
            {
                arr[i] = rand.Next();
            }

            var sw = new Stopwatch();

            sw.Start();

            Array.Sort(arr);

            //WaveMergeSort.Sort(arr);

            sw.Stop();

            Console.WriteLine(sw.ElapsedTicks);

Array.Sort => 12299
WaveSort => 36576

Злив в х3 рази.

Послухайте, шановний. Ви спочатку почитайте документацію по методу, а потім пишіть. learn.microsoft.com/...​-array-sort(system-array
Ніколи не пиши не перевіривши, а то виглядаєш трохи непрофесійно.
В документації написано, що в залежності від кількості, використовуються HeapSort або QuickSort. Вони обидва НЕ СТАБІЛЬНІ і до цієї статті не мають жодного відношення.

Ти про це ?

This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

Пц, так ти всюди інтегери сортируєш.
Яка різниця якщо в масиві 1 1 2 3 одиниці поміняли між собою місцями чи ні ?
Це дійсно коштує того, щоб просісти в швидкодії в три рази ?
Питань більше немаю, тобі с самого почату сказали про потребу порівняння з нормальним (мейнстрим) алгоритмами ))
Я чесно кажучи мав надію що воно хоч трохи норм працює, витратив 5хв свого часу на перевірку і поняв що повівся на якесь сміття. Далі без мене )

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

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

Всеж таки, веселий був топік.

Лол узбагойзя

Вопрос вполне резонный, если алгоритм рекламируется как stable sort, то надо хотя бы его реализация на типах данных, для которых stable sort имеет какой-то смысл (для обычных чисел, как Дід Панас заметил, результат stable sort и unstable sort одинаков.

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

Доречі, хтось може пояснити, навіщо на практиці той стейбл сорт.

Я писав вже про свій реальний випадок.
В протоколі є оригінальні повідомлення і є їх повтори. Є сквозний id повідомлення (не врапиться без спец. заходів). Для контроля якості і пошуку зниклих — сортуємо по id, але повтори мають бути після оригінальних повідомлень, щоб правильно рахувати часові характеристики.
А це як раз stable sort.

Більшість інших випадків повʼязана вже з сприйманням людиною, прямо або опосередковано. Наприклад, в wiki-движках є сортування таблиць кліком на заголовку стовпця. Якщо від додавання рядку зміниться порядок інших рядків — скарг не оберешся.

Група випадків вже у колег — коли використовували обʼєднання даних (повʼязані з картографією) з проміжним сортуванням даних точок. Алгоритми робили розрахунки і візуалізацію по цим даним. Логіка вкрай складна, зневадження теж. Коли від добавки значення, наприклад, с k=22 міняються місцями два значення з k=105, це спотворює відтворення результатів. Результат сортування ділиться на групи, кожна група має не змінюватись в залежности від змін в іншій. І знову ефект для UX — одне і те ж (центральні координати і масштаб) має відображатись однаково на всіх пристроях.

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

Да. Але явні алгорітми merge-групи на хвильку більш ефективні.

В протоколі є оригінальні повідомлення і є їх повтори. Є сквозний id повідомлення (не врапиться без спец. заходів). Для контроля якості і пошуку зниклих — сортуємо по id, але повтори мають бути після оригінальних повідомлень, щоб правильно рахувати часові характеристики.
А це як раз stable sort.

Для цього вистачить звичайний unstable з компаратором

  int CompareTo(Message msg1, Message msg2)
  {
      if(msg1.id != msg2.id)
          return msg1.id.CompareTo(msg2.id);
      else
          return msg1.timestamp.CompareTo(msg2.timestamp);
  }

В наведенних двох інших випадках все теж саме.

Да. Але явні алгорітми merge-групи на хвильку більш ефективні.

Алгоритм автора зливає стандартному Array.Sort в х3 рази.
З компаратором або розширеним ключом, ну буде зливати в х2 рази, а функціональність одна й таж сама.

Для цього вистачить звичайний unstable з компаратором

Ну проблема була ще в тому, что timestampʼу не можна було довіряти. А ось порядку збереження в логу — можна.

Алгоритм автора зливає стандартному Array.Sort в х3 рази.

Я говорив про stable sort в цілому. Ось наприклад Timsort зливатиме qsortʼу у скільки разів? Тільки на масивах од 100k елементів і з чимось складніше одного числа.
Судячи з того що в Python (і не тільки) його зробили стандартним sortʼом — якщо і зливає, то настільки незначно, що можна не враховувати. (Звісно, коли є допоміжна памʼять, і ще пара умов комфортної роботи.)

З компаратором або розширеним ключом, ну буде зливати в х2 рази

Все міряти треба. Ефекти кешу, наприклад, можуть зкривити всі показники.

В наведенних двох інших випадках все теж саме.

Поясніть, коли ласка, а то щось у мене великі сумніви.

Ну проблема була ще в тому, что timestampʼу не можна було довіряти. А ось порядку збереження в логу — можна.

То проблема дизайну системи. При нормальному дизайні timestamp в логах завжди має значення. Якщо не має, добавляйте OrderNumber. Полагатися на порядок запису, то елемент неявної логіки, що в реальних системах (СУБД, AWS, Azure логи) не використовується. Сьогодні логи писали так, завтра по іншому, після завтра в три потоку, після після завтра взагалі асинхронно та зробили партішин на кілька нод, а ви там десь порядок шукаєте.

Поясніть, коли ласка, а то щось у мене великі сумніви.

А в мене вже нема ніяких сумнівів. В всіх кейсах стейбл сорт можна досягти через розширення ключа сортування. Є деякі випадки криво спроектованих систем, но то їх проблеми.

А в мене вже нема ніяких сумнівів. В всіх кейсах стейбл сорт можна досягти через розширення ключа сортування. Є деякі випадки криво спроектованих систем, но то їх проблеми.

Какую проблему ты пытаешься решить, используя unstable sort вместо stable sort, что для этого стоит перепроектировать «криво спроектированную систему»

Реализации unstable sort немного быстрее, но на практике какое значение это имеет?

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

Мені реально смішно, як ви намагаєтесь екстраполювати досвід одного домену на інший :)

Ні, «дизайн системи» щоб timestamp можна було зробити адекватним — у тому випадку був неможливий. Специфіка така.
Вірю, що вона дуже рідка. Але ви просили прикладів — ось вам приклади (більше одного).

А в мене вже нема ніяких сумнівів. В всіх кейсах стейбл сорт можна досягти через розширення ключа сортування.

А, «теж саме» відносилось до «можна замінити».
Да, можна. Але може бути надто дорого.
Якщо вже дали функцію stable_sort, я припускаю, що вона краще зроблена, ніж самопал з розширенням ключа.

Ні, «дизайн системи» щоб timestamp можна було зробити адекватним — у тому випадку був неможливий

OrderNumber або Counter замість timestamp.
Чи та платформа не підтримувала інкремент інта ?

А, «теж саме» відносилось до «можна замінити».
Да, можна. Але може бути надто дорого.
Якщо вже дали функцію stable_sort, я припускаю, що вона краще зроблена, ніж самопал з розширенням ключа.

Добре, я зрозумів. Це щось типу дуже специфічної викртутки на СТО, що допомагає відкрутити болт при знятті фари, кріплення якої (чомусь) сховане десь за двигуном.

Чи та платформа не підтримувала інкремент інта ?

Не підтримувала адекватне зберігання того інта рядом з тілом повідомлення (це спрощуючи деталі, але адекватно).

Добре, я зрозумів. Це щось типу дуже специфічної викртутки на СТО,

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

Ні, я б сказав інакше. У більшости випадків, коли взагалі сортування корисне, його бажано робити стійким

Не пиши дурні.
Всі СУБД що я знаю — не стійке сортування.
Azure, AWS логи — не стійке сортування
.NET, Java — всі мейнстрим сортування, не стійке сортування.

У автора стійке ! Але трошки тре оптимізувати в кілька разів, ну то таке.
Може продасть в контору в якій не змогли timestamp нормально заповнити.

Не пиши дурні.
Всі СУБД що я знаю — не стійке сортування.

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

Може продасть в контору в якій не змогли timestamp нормально заповнити.

Смішний ти. Там таке в принципі не треба, там kdb+ — база розгляду (а зазвичай ще специфічніше;))

У автора стійке !

Ну вообще не только у автора.

doc.rust-lang.org/...​ve.slice.html#method.sort

Sorts the slice.

This sort is stable (i.e., does not reorder equal elements) and O(n * log(n)) worst-case.

.NET

ой, а что тут у нас?
learn.microsoft.com/...​able.orderby?view=net-8.0

This method performs a stable sort; that is, if the keys of two elements are equal, the order of the elements is preserved.

docs.python.org/3/howto/sorting.html

Sorts are guaranteed to be stable. That means that when multiple records have the same key, their original order is preserved.
ой, а что тут у нас?
learn.microsoft.com/...​able.orderby?view=net-8.0

А у вас тут LINQ, що появився в 2007 році, набагато пізніше чим створили .NET. Має deferred виконання, та працює набагато повільніше (як і весь LINQ) чим основний алгоритм сортування в .NET Array.Sort

А у вас тут LINQ, що появився в 2007 році, набагато пізніше чим створили .NET. Має deferred виконання, та працює набагато повільніше (як і весь LINQ) чим основний алгоритм сортування в .NET Array.Sort

Какой именно алгоритм является «основным» — вопрос спорный. А то, что в .NET реализована стабильная сортировка — факт.

В ФІДО-ехах ми таких тролів дуже швидко банили. Золоті були часи...

Просто нагадаю, що в реальному житті багато задач, в яких обробляються данні, які не належать обробнику і треба брати те, що дають, не намагатись «перепроектувати систему», яка тобі не належить.

А ось порядку збереження в логу — можна.

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

В загальному випадку — да.
В конкретному — лог писався власними засобами як, грубо кажучи, insert в таблицю в памʼяті, яка скидалась після робочого часу. Специфіка біржи. Все своє крім базового движка БД дуже специфічного типу.

то надо хотя бы его реализация на типах данных, для которых stable sort имеет какой-то смысл

Тогда надо сразу мерить при дорогом сравнении (да хоть sleep() в функцию сравнения вставить).
Но вообще это вполне честный подход — мерить среди родственных по требованиям алгоритмов даже если данные недостаточно важны.

Подставить там можно любой тип.

Так что «Дід Панас» откровенно додолбался до столба.

Подставить там можно любой тип.

Для этого надо хотя бы generic реализацию запилить, чтоб не получилось как в соседнем топике с самым быстрым trie, который показывает свою быстроту только на 32-битных числах.

как в соседнем топике с самым быстрым trie,

Можна посилання ?

ооо, то це вже зовсім інша справа.
Є код бенчмарку, скачав, перевірив на своєму компьютері.
В мене трохи гірші результати, але в цілому це схоже на правду
Для інтів
github.com/...​t_seq_32bits.png?raw=true
Для довгих ключів
github.com/...​rand_128bits.png?raw=true

До речі, як я зрозумів з основної сторінки, в тому контейнері, функціональності значно більше ніж в хештаблиць
raw.githubusercontent.com/...​Images/functionality2.png

Тобто це той самий випадок, коли «стабільний» алгоритм виграє у всіх «не стабільних» алгортимів не тільки за функціональністю, а навіть за швидкодією.

Доречі, якщо автор не напицтів, та в контейнері сортовані ключі, то маємо побочне сортування рандом інтів
202мс => 9М на iCore5.
А це на хвильку, майже в 15 разів швидше чим заявлено у топік стартера
56мс => 200k.

github.com/...​_rand_32bits.png?raw=true

Але в коді, я так по діагоналі подивився, розібратися дуже важко. Тому не можу сказати, справді сортовані ключі там чи ні після вставки. Може хтось перевіряв.

ты издеваешься?

В чому саме? Тобі не вдалося запустити той бенчмарк на свому компьютері? Можу допомогти.

А це на хвильку, майже в 15 разів швидше чим заявлено у топік стартера

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

Ты сегодня Витя?

Результати на сортованому(в обидва боки) масиві зрозуміло чого такі гарні — вони просто робляться за лінійний час. Парабола теж, просто половину перевернути. На рандомних данних покращення незначне, і справа радше в імплементації ніж в самому алгоритмі

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

Неочевидно, мерджсорт можно більш ефективно розпалелити(а різниця незначна не в абсолютних значеннях, а й в пропорції). Ваш алгоритм дійсно цікавий, але я не думаю що він краще добре оптимізованих класичних. Як не як їх розробляли десятки років
P.S. Перші 4 бенчмарки нерепрезентативні)

Я просто поділився реалізацією нового підходу і не претендую на використання мого підходу всім. Його теж можна розпаралелити, в чому проблема.
Нижче в коментах навів бенчмарки чисто рандомних масивів і тут продублюю:

int[] CreateRandomArray(int size)
{
	var array = new int[size];
	var rand = new Random();
	for (int i = 0; i < size; i++)
		array[i] = rand.Next(0, 9999);
	return array;
}
N = 1M, Wave Sort: 312.0242ms, Merge Sort: 364.8288ms
N = 2M, Wave Sort: 638.6731ms, Merge Sort: 740.0590ms
N = 5M, Wave Sort: 1699.7112ms, Merge Sort: 2004.5810ms
N = 10M, Wave Sort: 3462.7547ms, Merge Sort: 4011.3034ms

А як його розпалелити? Ви не знаєте завчасно розміри впорядкованих сегментів як в квіксорті/мерджсорті

Після знаходження всіх підмасивів методом поділу на 2, як і скрізь, розділяй і володарюй.

Так тут же масив невпорядкований. Щоб знайти сегменти вам знадобитися О(n) часу і паралельність вам не допоможе

Масив waves після першого проходу вже зберігає індекси всіх підмасивів, нічого не потрібно шукати.

Дійсно, не подумав. Тоді можно зручно паралелізувати і зробити швидким

Мені реально цікаво, в яких областях _зараз_ ще мають значення алгоритми сортування і, тим більше, такі тонкі оптимізації.

За ~25 років роботи в галузі я разів 5, мабуть, викликав сортування (я не кажу про варіанти на зразок «du -akx | sort -rn | less», і то вони від ліні) і лише один — навмисно стійке сортування — коли черга повідомлень за їх id і треба було щоб спочатку йшли оригінали, потім повторення.

Практично ж ~80% випадків коли щось таке вимагається — реалізуються через хеш-таблиці (хеш-мапи) і ~20% — мапи на деревах всіх видів (AVL, RB, B/B+/etc.) — бо випадків, коли всі дані приходять на вхід одночасно, майже нема, а щоб поступово вони йшли — майже завжди.

Тому, мабуть, ця робота цікава в плані наповнення астралу ноосфери, але практичної цінності має близько до нуля. Або покажіть, де сортування масивів, що лежать повністю в оперативній памʼяті, ще має велике значення і 1-2% вартують безсонних ночей.

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

Але ж ви користуєтесь базами данних і швидше за все там сортуються результати для ваших продуктів. Ось там сортування і використовується.

Коли в БД order by не по готовому ключу... ну згоден, у такому випадку — має якийсь сенс. Але сама така ситуація частіше за все означає неефективне налаштування бази, чи — якщо грамотно спроектовано — настільки малі виборки, що там та оптимізація неважлива на тлі інших витрат.

(І до речі — у БД рідко буває дороге порівняння вже маючи два рядки вихідних даних.)

Знову ж, є домени, які можуть це використовувати досить серйозно, наприклад, фізичні, медичні чи біологічні дослідження.

І воно вміщується в оперативну памʼять? Якщо ні — треба перерозраховувати алгорітми з урахуванням цього.

Ви пробували порівняти продуктивність у випадку, коли замапили і сортуєте, наприклад, 100GB файл при 16GB оперативи? І при дійсно складному порівнянні?

Ні, не пробував, поки що це як концепт і ідея

Если я правильно понимаю, волны направленные в обратном направлении можно не разворачивать — просто мерджить с конца а не с начала. Но придется немного заморочится чтобы не потерять стабильность

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

Я-бы этот признак прямо в знак индекса запихнул %)

Я згоден, що Тім Петерс покращив мерж сорт, беручи підмасиви заданої довжини, сортуючи їх за допомогою insertion sort, а потім зливаючи їх алгоритмом мерж сорта.
Але знову, кількість операцій не оптимальна.
В мене інше рішення і навіть метод злиття інший, ніж класичний.
Алгоритми сортування зазвичай подаються на прикладі масиву цілих чисел. А тепер уявіть, що ви сортуєте об’єкти по ключам складніших типів або цих ключів може бути декілька і ціна оперції порівняння буде значно вищою. Ось тут всі і згадають про оптимізацію кількості порівнянь.

У Тімсорт так саме як у вас знаходяться піддіапазони з послідовно зростаючими/спадаючими даними, потім вони мерджаться, щоб мінімізувати додаткову пам’ять мердж відбувається тільки при виконанні певних умов щодо розміру цих піддіапазонів. Якщо мердж зараз не є вигідним, піддіапазон додається в стек (щоб не порушити стабільність і зливати тільки суміжні піддіапазони). Якщо діапазони все одно замалі, вони дорощуються до певної мінімальної довжини за допомогою InsertionSort. Для зменшення кількості порівнянь при злитті великих піддіапазонів додатково використовується «галапування» (експоненційний пошук, де крок збільшується на певний фактор, поки не буде «перебор», а потім бінарним діленням в межах останньої «виделки»), щоб швидше знайти голову та хвіст піддіапазонів, які не перекриваються і тому можуть бути просто скопійовані у вихідний масив без додаткових порівнянь, а середня частина, що перекривається у двох піддіапазонах, вже зливається за звичною схемою по одному чемпіону по черзі.

Тобто ця ідея з використанням «хвиль» вже давно опрацьована і оптимальні стратегії в цьому напрямку досліджені і використовуються в стандартних бібліотеках (принаймні в Python та Java саме цей алгоритм використовується для стабільного сортування).

Якщо операція порівняння задорога, то можна або спробувати зробити штучні ключі, які обчислюються один раз для кожного елементу перед сортуванням і порівняння яких для двох елементів дасть той самий результат, що й порівняння самих елементів, і далі вже сортувати ті ключі (вони зберігають індекс оригінального елементу) і отримати відсортований індекс для початкових даних по обраному критерію (можна створити кілька індексів по різним критеріям без тасування самих даних). Другий спосіб — це відсортувати по одному критерію, а потім — по іншому, якщо алгоритм сортування стабільний, то на виході отримуємо сортування по всім зазначеним критеріям (найбільш значущий використовується для сортування останнім).
Зазвичай, якщо порівняння коштують дорого, використовується якийсь з варіантів en.wikipedia.org/wiki/Bucket_sort що дозволяє поділяти на групи, які можна впорядкувати між собою, і подальші порівняння відбуваються лише між елементами в межах однієї групи.

1. Де порівняння з класичним Bubble Sort ?
2. Де код бенчмарку ? Бенчмарк з кодом та залізом то є на 50% п***ьош, який потрібно переміряти на свому залізі та на своїх данних. А без коду — то вже 100% п***ьош.
3. Чому порівняння з класичним мержсорт, це не мейнстрімове сортування. Мейнстрім то квіксорт чи тімсорт, особливо на малих данних.
4. Що то за синтетика в вхідних данних, якісь параболи. Вперше чую. Ось рандом то зрозуміло і там якісь лічені відсотки перевага, що навіть не смішно.
5. Порівнювати свій алгоритм на маленьких обємах данних, це досить кумедно. На малих обємах цвяхи можна забивати навіть мікроскопом або бабл сортом.
6. З чого ви взяли що хтось використовує класичний merge sort без оптимізацій, а не з якимось cuda що дає х100 перевагу з тим що ви тут щось наміряли.

Коротче, багато питань і мало відповідей.

Дякую за фідбек. Відповідаю:
1. З bubble sort немає сенсу порівнювати, бо на значних об’ємах він виграє тільки на вже відсортованому масиві.
2. Код бенчмарку не наводив, думаю, що тут кожен його напише за 10 хв, взявши коди відповідних алгоритмів. За залізо згоден, але тести проводились на тій самій машині, і тут вже відіграє роль в кількості операцій порівняння і заміни.
3. Чому ж мерж сорт не мейнстрім? Який по вашому алгоритм використовується в базах даних для сортування великих об’ємів? Timsort — то похідний від мерж сорту, а quick sort — нестабільний, тому тут йому точно не місце.
4. За назви даних вибачте, просто показав параболу, як приклад з великими діапазонами сортованих підмасивів всередині.
5. Ну я б не сказав, що 200к — то малий об’єм даних і bubble sort там би точно загнувся.
6. Згоден, що алгоритми використовують з оптимізаціями і паралельними обчисленнями. Те ж саме можна зробити і з даним алгоритмом. Я всього лише показав підхід з аналізом даних і формуванням підмасивів для злиття, які вже природньо відсортовані в масиві. Це, як на мене, дає мінімальну кількість операцій, що є важливим для таких алгоритмів.

З бабл сортом то був гумор.
З яким я бачу в когось не дуже.

Чому ж мерж сорт не мейнстрім? Який по вашому алгоритм використовується в базах даних для сортування великих об’ємів?

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

Timsort — то похідний від мерж сорту,

Ні. То є гібрид.

а quick sort — нестабільний, тому тут йому точно не місце.

А ваш вже доведено стабільний?
Трохи фальстартнули, треба було з пятниці починати.

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

Доберусь до компа і пришлю тести для мільйону)

Я досі не розумію змісту того всього. Ну виграєте ви на мільйоні 5%, чи програєте ті самі 5%. Далі потрібно буде розбиратись, що там з чанками, що з додатковою памятю. Що ви накрутили щоб погіршити конкурента, та що накрутили в себе, щоб покращити свої результати.
Зміст того всього. Як ваш алгоритм гарно сортує якісь параболічні дані, то так його й назовіть. Може комусь в світі потрібно ті параболи чи синусоїди сортувати, знайде той алгоритм, та виграє в свому коді ті заявлені мілісекунди.

Доречі мерж сорт на великих данних працює з вінчестерами. Тобто основна перевага merge sort в тому що він не задрачує механічну головку вінчестера, томущо той самий seek time ну дуже повільний. І тут витягнули несчастний мерж повністю в ram і давай йому навалювати без привязки до технічних данних носія інформації.
Коротче треш і содомія.

Я ні з ким не збирався конкурувати і нічого не накручував. Алгоритм лежить на GitHub, можна брати і перевіряти без «моїх накруток».
Просто хотів поділитись, а ви якийсь холівар з того розводите і ще й звинувачуєте мене бездоказно і безпідставно.
Візьміть і порівняйте кількість операцій і все стане ясно.
Даний приклад і бенчмарки на цілих числах відбуваються, де ціна операції порівняння низька.
Уявіть, якщо порівняння буде по тексту або ще й по декільком ключам. От тоді кількість операцій стане в нагоді і перетвориться на більш суттєвий часовий проміжок.
Ну і щодо Timsort (ще раз кажу, що ні в якому разі не хочу применшити чи чимось образити розробників існуючих алгоритмів):
1. Візьмемо масив розміром 32 (як і дефолтовий run у Timsort) повністю сортований по спаданню (найгірший випадок для Timsort)
2. Тімсорт виконає 31*32/2 = 496 замін і стільки ж порівнянь
3. Wave Sort зробить 31 порівняння і 16 замін.
-----------------------
1. Візьмемо wave array (він же синусоїда) розміром 32 (найгірший випадок для Wave Sort)
2. Wave Sort зробить 123 порівняння і 98 замін
3. Timsort зробить 208 порівняннь і 200 замін
-----------------------
Як і обіцяв, цифри по мільйонам (якщо захочете вірити):
N = 1M, Wave Sort: 312.0242ms, Merge Sort: 364.8288ms
N = 2M, Wave Sort: 638.6731ms, Merge Sort: 740.0590ms
N = 5M, Wave Sort: 1699.7112ms, Merge Sort: 2004.5810ms
N = 10M, Wave Sort: 3462.7547ms, Merge Sort: 4011.3034ms

N = 1M, Wave Sort: 312.0242ms, Merge Sort: 364.8288ms

Виграти аж 52 міллісекунди.
Побережіть калорії мязів пальць тих, кто буде клацати кнопку завантажити та встановити. Калорії дорожче коштують.

Але то 14% як не як і це на цілих числах ;-)

А має бути щонайменьше х2-х10 щоб технологія мала шанс. Коли я йду в магазин і думаю який вінчестер мені купити, що пише 100 мб/сек або 114мб/сек, мабуть фото собаки чи кота буде відігравати більшу роль на етикетці. А в вас то навіть не кінцева характеристика, а щось що в реальному пристрої або флоу розмиється до виграшу в 0.001% від заявленої швидкодії.

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

Правила хорошего тона — выкладывать код бенчмарков, что его можно было скачать на свой компьютер, запустить и сравнить результаты. Большинство людей не настолько заинтересованы в вашем проекте чтоб самостоятельно писать код бенчмарков и реализовывать алгоритмы, с которыми вы сравниваете ваш алгоритм (почему-то сам merge sort, с которым вы сравниваете, вы решили не чекинить).

По сути никто не сможет перепроверить ваши результаты кроме людей с избытком свободного времени, среди которых скорее всего не будет компетентных людей для того, чтоб сравнить результаты бенчмарков и задавать неудобные вопросы.

Оце прям дуже цікаво. Виявляється що і в таких наче сталих областях як алгоритми сортування можна зробити покращення!

github.com/...​WaveMergeSort.cs#L99-L117

		/// <summary>
		/// Reverses the sequence of the elements in a range of the specified array.
		/// </summary>
		/// <param name="arr">The one-dimensional, zero-based array to reverse.</param>
		/// <param name="left">The starting index of the range to reverse.</param>
		/// <param name="right">The ending index of the range to reverse.</param>
		private static void reverse(int[] arr, int left, int right)
		{
			int i = left;
			int j = right;
			while (i < j)
			{
				var tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
				i++;
				j--;
			}
		}

Array.Reverse чем не угодил?

Так це ж базовий алгоритм, що не мав би спиратись на інші функції. Тоді можно було і Array.Sort заюзати.

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

Можете дать оценку Space Complexity конкретно касаемо использования памяти стека?

O(n + k), де n це для злиття, як і в класичному Merge Sort, k — для допоміжного масиву для збереження індексів хвиль.
В даному випадку k = n/3 + 2, тож загальний виходить O(4n/3 +2).

Константи хіба не відкидаються?

Но это не использование стека. Использование стека в merge sort log(n), что на любых «гиганстких» входных данных не переполнит стек (проблема, о который вы выше упомянули).

Ви праві, повернув рекурсію. Складність зараз O(n + k), де n це для злиття, як і в класичному Merge Sort, k — для допоміжного масиву для збереження індексів хвиль, k <= n/2.

Підписатись на коментарі