Изменения

Разделим исходную перестановку <tex>\pi</tex> на блоки <tex>C_j = \{\pi_{(j-1)m + 1},~\pi_{(j-1)m + 2},~\dots, ~\pi_{(j-1)m + m}\}</tex>. Получим сортированные варианты этих блоков <tex>C_j^S</tex>. При лобовой {{Acronym|цифровой|radix}} сортировке мы получим <tex>O(\frac{n}{m}n)</tex>. Дополним каждый элемент <tex>\pi</tex> номером блока, в котором он находится и смещением в этом блоке. Теперь, {{Acronym|рассматривая номер блока как старший разряд, элемент как младший разряд|по смещению внутри блока не сортируем}}, можно сортировать цифровой сортировкой за линейное время <tex>O(n)</tex>.==== Пример ====Пусть <tex>m = 5</tex>. Исходно:{| class="wikitable" style="text-align:center"| Блок ||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#8080FF"|3||style="background:#8080FF"|3|-|<tex>\pi</tex>||style="background:#FF8080"|9||style="background:#FF8080"|3||style="background:#FF8080"|10||style="background:#FF8080"|4||style="background:#FF8080"|8||style="background:#80FF80"|1||style="background:#80FF80"|2||style="background:#80FF80"|12||style="background:#80FF80"|6||style="background:#80FF80"|5||style="background:#8080FF"|7||style="background:#8080FF"|11|-|Смещение||style="background:#FF8080"|1||style="background:#FF8080"|2||style="background:#FF8080"|3||style="background:#FF8080"|4||style="background:#FF8080"|5||style="background:#80FF80"|1||style="background:#80FF80"|2||style="background:#80FF80"|3||style="background:#80FF80"|4||style="background:#80FF80"|5||style="background:#8080FF"|1||style="background:#8080FF"|2|}После сортировки:{| class="wikitable" style="text-align:center"|Блок ||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#FF8080"|1||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#80FF80"|2||style="background:#8080FF"|3||style="background:#8080FF"|3|-|<tex>\pi</tex> ||style="background:#FF8080"|3||style="background:#FF8080"|4||style="background:#FF8080"|8||style="background:#FF8080"|9||style="background:#FF8080"|10||style="background:#80FF80"|1||style="background:#80FF80"|2||style="background:#80FF80"|5||style="background:#80FF80"|6||style="background:#80FF80"|12||style="background:#8080FF"|7||style="background:#8080FF"|11|-|Смещение ||style="background:#FF8080"|2||style="background:#FF8080"|4||style="background:#FF8080"|5||style="background:#FF8080"|1||style="background:#FF8080"|3||style="background:#80FF80"|1||style="background:#80FF80"|2||style="background:#80FF80"|5||style="background:#80FF80"|4||style="background:#80FF80"|3||style="background:#8080FF"|1||style="background:#8080FF"|2|}