Math
Перегони сортувань
Три сортування біжать по одному масиву з однаковою швидкістю в ПОРІВНЯННЯХ, і першим фінішує те, що спитало менше. Вирішує не розмір, а безлад: на впорядкованому вході вставки беруть 63 порівняння, а швидке — 2016.
Що відбувається
Три доріжки, один масив і один спільний бюджет роботи: усі три сортування просуваються на однакову кількість порівнянь — або переміщень, якщо перемкнути одиницю, — тож першим фінішує те, якому потрібно найменше цієї одиниці, а не те, що намальоване швидше. На всіх доріжках одна мова: два порівнювані ключі обведені золотом, щойно записаний ключ спалахує зеленим, опорний елемент позначений червоним, оброблювана ділянка взята в дужку, елементи на своєму остаточному місці отримують зелену підставку, а ключ, який тримає сортування вставками, висить над щілиною, куди опуститься. Передбачте переможця до кнопки «Старт» або ведіть перегони по одній одиниці. Спробуйте входи: на відсортованому масиві вставки фінішують майже одразу, а швидке сортування з останнім опорним потрапляє у свій найгірший випадок; зворотний порядок — найгірший випадок вставок; з повторюваними ключами колір — це місце у вході, і злиття зберігає порядок рівних ключів, а швидке їх перемішує. Кожна доріжка показує й справжній час прогону на цьому комп'ютері — третю величину, ніколи не одиницю перегонів.
Рівняння модуля
Рівняння n елементів, а перегони ведуться в ПОРІВНЯННЯХ - у тій величині, про яку йдеться у формулах сортування вставками ПЕРЕМІЩУЄ елемент рівно стільки разів, скільки інверсій має масив: тотожність на КОЖНІЙ перестановці, перевірена по всіх n! для n <= 8 порівняння вставками = інверсії + (n − 1) − (префіксні мінімуми при i >= 1); середнє = n(n−1)/4 + n − H_n РІВНО: n = 8 -> 19.282142857142858; n = 64 -> 1067.2561090962943 швидке сортування (Ломуто, останній елемент як опорний) середнє = 2(n+1)H_n − 4n РІВНО: n = 8 -> 16.921428571428571; n = 64 -> 360.70581748175005 найгірший випадок сортування злиттям = n·ceil(lg n) − 2^ceil(lg n) + 1 - це формула, а не оцінка: 321 при n = 64, проти ceil(lg n!) = 296, нижньої межі для БУДЬ-ЯКОГО сортування порівняннями ці дві величини рівні при n <= 4 і розходяться після цього; сортування злиттям також записує n·lg n елементів незалежно від входу - 384 при n = 64 64 елементи, усі місця перемішані: 1001 інверсія; вставками 1057 порівнянь / 1001 переміщення, злиттям 307 / 384, швидке 352 / 306 64 елементи, відсортований вхід: вставками 63, злиттям 192, швидке 2016 - і 2016 дорівнює n(n−1)/2, НАЙГІРШОМУ випадку швидкого сортування злиття випереджає вставки при 15 перемішаних місцях із 64 (269 проти 246): поріг визначає безлад, а не розмір - на випадковому вході злиття попереду починаючи з n = 4 однакові ключі, 64 елементи на 8 значень: пар, залишених у зворотному порядку - вставками 0, злиттям 0, швидке 77
