J-сортування

Своє бачення пірамідальної сортування запропонував і скромний трудівник Університету Манітоби Джейсон Моррісон . При цьому спосіб в деяких випадках

за швидкістю наближається до O (n ).

Джейсон Моррісон (Jason Morrison, метод сортування названий на честь автора) запропонував щось протилежне — «Для оптимізації треба не ускладнювати, а максимально спрощувати».

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

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

Спочатку потрібно здійснити побудову незростаючої купи. В результаті менші елементи піднімуться у верхні вузли піраміди (що відповідатиме лівій половині масиву), найменший елемент взагалі виявиться в корені. Чим вище елементи знаходяться в кроні дерева — тим більш впорядкованою буде відповідна частина масиву. Елементи знаходяться ближче до листя дерева (їм буде відповідати друга половина масиву) матимуть менш упорядкований вигляд, оскільки вони не порівнювалися, а просто були відтіснені на задвірки в результаті переміщення їх батьків.

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

Збудувавши такі собі близнючки-пірамідки, отримуємо багато в чому впорядкований масив. Довершує справу сортування вставками . Цей алгоритм має вельми скромну середню складність за часом O (n2), але творить чудеса на масивах, які вже майже відсортовані.