Timsort

Набори вставляються у стек. Якщо ${\displaystyle \left\vert Z\right\vert \leq \left\vert Y\right\vert +\left\vert X\right\vert }$ , тоді X і Y об'єднуються і замінюються у стеку. Таким чином, злиття продовжується до тих пір, поки всі набори не задовольнять і. ${\displaystyle \left\vert Z\right\vert >\left\vert Y\right\vert +\left\vert X\right\vert }$ та іі. ${\displaystyle \left\vert Y\right\vert >\left\vert X\right\vert }$

Timsort — це стабільний алгоритм сортування (порядок елементів з однаковими значеннями зберігається) і прагне виконувати збалансоване злиття (таким чином злиття об'єднує набори подібного розміру).

Для досягнення стабільності сортування об'єднуються лише послідовні набори. Між двома послідовними наборами всередині набору може бути елемент з однаковим значенням. Об'єднання цих двох наборів змінило б порядок однакових значень. Приклад цієї ситуації ([]- це впорядковані набори): [1 2 2] 1 4 2 [0 1 2]

У гонитві за збалансованим злиттям, Timsort розглядає три набори на вершині стека, X, Y, Z і підтримує інваріанти: і. ${\displaystyle \left\vert Z\right\vert >\left\vert Y\right\vert +\left\vert X\right\vert }$

іі. ${\displaystyle \left\vert Y\right\vert >\left\vert X\right\vert }$

Якщо будь-який з цих інваріантів порушується, Y зливається з меншим з X або Z, і інваріанти перевіряються знову. Після того, як інваріанти задовільнили умову, можна починати пошук нового впорядкованого набору в даних.[10] Ці інваріанти підтримують злиття як приблизно збалансовані.

Щоб об'єднати набори, Timsort копіює елементи меншого масиву (X на цій ілюстрації) у тимчасову пам'ять, потім сортує та заповнює елементи в остаточному порядку в об'єднаний простір X та Y.

Початкова реалізація сортування злиттям не виконується без використання додаткового простору, тобто використовує N (розмір даних). Реалізації сортування об'єднаннями без використання додаткової пам'яті існують, але мають великі витрати часу. Timsort натомість виконує сортування з меншими витратами часу, використовуючи невеликий додатковий простір(<N)(щоб досягти середнього значення).

По-перше, Timsort виконує двійковий пошук, щоб знайти місце, куди перший елемент другого набору буде вставлений у першому впорядкованому наборі, зберігаючи його впорядкованим. Потім він виконує той самий алгоритм, щоб знайти місце, куди буде вставлено останній елемент першого набору у другому впорядкованому наборі, зберігаючи його впорядкованим. Елементи до та після цих розташувань уже на своїх правильних місцях і їх не потрібно об'єднувати. Потім менший із решти елементів двох наборів копіюється у тимчасову пам'ять, а елементи об'єднуються з більшим набором, звільняючи простір. Якщо перший набір менший, злиття починається з початку; якщо другий менший, злиття починається в кінці. Ця оптимізація зменшує кількість необхідних переміщень елементів, час роботи та тимчасові накладні витрати пам'яті в загальному випадку.

Приклад: два набори [1, 2, 3, 6, 10] та [4, 5, 7, 9, 12, 14, 17] повинні бути об'єднані. Зауважте, що вони вже відсортовані окремо. Найменший елемент другого набору - 4, і його слід додати на четвертій позиції першого набору, щоб зберегти його порядок (припускаючи, що перша позиція набору дорівнює 1). Найбільший елемент першого набору - 10, і його слід додати на п'ятій позиції другого набору, щоб зберегти його порядок. Тому [1, 2, 3] та [12, 14, 17] вже знаходяться у своїх остаточних положеннях, а набори, в яких потрібні переміщення елементів, - [6, 10] та [4, 5, 7, 9]. Маючи ці знання, нам потрібно лише виділити тимчасовий буфер розміром 2 замість 5.

Об'єднання можна здійснювати в обох напрямках: зліва направо, як у традиційному сортуванні, або справа наліво.

Елементи (на які вказує синя стрілка) порівнюють, а менший елемент переміщують у кінцеве положення (на яке вказує червона стрілка).

Індивідуальне злиття наборів R1 та R2 зберігає кількість послідовних елементів, вибраних із циклу. Коли це число досягає мінімального порогу галопу (min_gallop), Timsort вважає, що ймовірно, що багато послідовних елементів все ще можуть бути вибрані з цього запуску, і перемикається в режим галопу. Припустимо, що R1 відповідає за його запуск. У цьому режимі алгоритм виконує експоненціальний пошук, також відомий як галопуючий пошук, для наступного елемента x циклу R2 у прогоні R1. Це робиться у два етапи: перший знаходить діапазон (2 ^k — 1, 2 ^k+1 — 1) де x. Другий етап виконує двійковий пошук елемента x у діапазоні, знайденому на першому етапі. Режим галопу — це спроба адаптувати алгоритм злиття до шаблону інтервалів між елементами в наборів.

Усі червоні елементи менші за сині (тут, 21). Таким чином, вони можуть бути переміщені фрагментом до остаточного масиву.

Галоп не завжди ефективний. У деяких випадках режим галопу вимагає більше порівнянь, ніж простий лінійний пошук . Відповідно до орієнтирів, розроблених розробником, галоп вигідний лише тоді, коли початковий елемент одного пробігу не є одним із перших семи елементів іншого прогону. Це передбачає початковий поріг 7. Щоб уникнути недоліків режиму галопування, виконуються дві дії: (1) Якщо галопування виявляється менш ефективним, ніж бінарний пошук, режим галопу виходить. (2) Успіх або невдача галопу використовується для коригування min_gallop . Якщо вибраний елемент з того самого масиву, який повертав елемент раніше, min_gallop зменшується на одиницю, таким чином заохочуючи повернення до режиму галопу. В іншому випадку значення збільшується на одиницю, тим самим перешкоджаючи поверненню в режим галопу. У разі випадкових даних значення min_gallop стає настільки великим, що режим галопу ніколи не повторюється.[11]

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

Алгоритм Timsort шукає впорядковані послідовності мінімального розміру(minruns), для виконання їх сортування.

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

Minrun вибирається з діапазону від 32 до 64 включно, таким чином, що розмір даних, поділений на minrun, дорівнює або трохи менший за потужність двох. Остаточний алгоритм бере шість найбільш значущих бітів розміру масиву, додає один, якщо будь -який з решти бітів встановлено, і використовує цей результат як minrun. Цей алгоритм працює для всіх масивів, включаючи ті, що менші за 64; для масивів розміром 63 або менше це встановлює minrun рівним розміру масиву, а Timsort зменшує до сортування вставки.