Изменения

* Пройдем по исходному массиву <tex>A</tex> и запишем в <tex>P[i]</tex> количество структур, ключ которых равен <tex>i</tex>. Это можно сделать за <tex> O(n)</tex>[[Файл:Building_P.png]] * Условно Мысленно разобьем массив <tex>B</tex> на <tex>k</tex> блоков, длина каждого из которых равна соответственно <tex>P[1]</tex>, <tex>P[2]</tex>, ..., <tex>P[k]</tex>.[[Файл:Splitting_B_w_colors.png]] * Теперь массив <tex>P</tex> нам больше не нужен. Превратим его в массив, хранящий в <tex>P[i]</tex> сумму элементов от <tex>0</tex> до <tex>i-1</tex> старого массива <tex>P</tex>. [[Файл:P_after_adding.png]] * Теперь "сдвинем" массив <tex>P</tex> на элемент вперед: в новом массиве <tex>P[0] = 0</tex>, а для <tex>i > 0</tex> <tex>P[i] = P_{old}[i-1]</tex>, где <tex>P_{old}</tex> - старый массив <tex>P</tex>. <br> Это делается можно сделать за один пробег проход по массиву <tex>P</tex>, то есть имеет сложность причем одновременно с предыдущим шагом. <br> После этого действия в массиве <tex> O(k)P</tex> будут хранится индексы массива <tex>B</tex>. <tex>P[key]</tex> указывает на начало блока в <tex>B</tex>, соответствующего ключу <tex>key</tex>.[[Файл:P_as_array_of_pointers.png]] * Произведем саму сортировку. Еще раз пройдем по исходному массиву <tex>A</tex> и для всех <tex>i \in [0, n-1]</tex> будем помещать структуру <tex>A[i]</tex> в массив <tex>B</tex> на место <tex>P[A[i].key]-</tex>, а затем увеличивать <tex>P[A[i].key]</tex> на <tex>1</tex>. Здесь <tex>A[i].key</tex> {{---}} это ключ структуры, находящейся в массиве <tex>A</tex> на <tex>i</tex>-том месте. Затем увеличим <tex>P[A[iФайл:Sorting_A.png].key]</tex> на единицу.