Изменения

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