Изменения

<b> База</b>: <tex> n = 1 </tex>. Очевидно, что алгоритм работает верно, потому что в таком случае мы просто сортируем младшие разряды какой-то заранее выбранной стабильной устойчивой сортировкой.

<b> Переход</b>: Пусть для <tex> n = k </tex> алгоритм правильно отсортировал элементы по <tex> k </tex> младшим разрядам. Покажем, что в таком случае, при сортировке по <tex> (k + 1) </tex>-ому му разряду, объекты также будут отсортированы в правильном порядке.

Вспомогательная сортировка разобьет все объекты на группы, в которых <tex> (k + 1) </tex>-ый й разряд объектов одинаковый. Рассмотрим такие группы. Для сортировки по отдельным разрядам мы используем стабильную устойчивую сортировку, следовательно порядок объектов с одинаковым <tex> (k + 1) </tex>-ым м разрядом не изменился. Но по предположению индукции по предыдущим <tex> k </tex> разрядам объекты были отсортированы правильно, и поэтому в каждой такой группе объекты будут отсортированы верно. Также верно, что сами группы находятся в правильном относительно друг друга порядке, а, следовательно, и все элементы отсортированы правильно по <tex> (k + 1) </tex>-ым м младшим разрядам.