Изменения

Пусть размер остатка <tex> s </tex>. Начиная с конца, разобьем наш массив на подряд идущие группы длиной s. Используя квадратичную или более быструю сортировку, которая требует дополнительной памяти <tex> O(1) </tex>, отсортируем подмассив длиной <tex> 2s </tex>, который находится в конце. На последних <tex> s </tex> местах будут находится находиться s максимальных элементов. Оставшаяся часть представляет собой массив, содержащий две отсортированные части, причем размер второй равен<tex> s </tex>. По аналогии с шагом 3 в обратном порядке сливаем группы длиной <tex> s </tex>.