Изменения

[[Цифровая сортировка]] каждого блока отдельно будет давать нам время работы <tex>O \left(\dfrac{n}{m}n \right) = O \left(\dfrac{n^2}{m} \right)</tex>. Чтобы отсортировать их за линейное время, дополним Дополним каждый элемент номером его блока и получим пары <tex>\langle\lceil i/m\rceil,\pi_i\ranglepi</tex>номером блока, в котором он находится и смещением в этом блоке. Цифровая сортировка этих парТеперь, если принимать за рассматривая номер блока как старший разряд номер блока, а за элемент как младший значение элементаразряд (по смещению внутри блока не сортируем), будет работать можно сортировать цифровой сортировкой за линейное время <tex>O(n)</tex>, потому что значения элементов и номера блоков не превосходят <tex>n</tex>. Перестановка смещений, образованная в сортированном блоке есть не что иное, как обратная перестановка перестановки, элементы которой соотносятся между собой как элементы исходного блока. Находим обратную перестановку к найденной, назовем ее <tex>\xi</tex>.