Аннотация:Изучается число сравнений, достаточное для сортировки n элементов линейно упорядоченного множества. Показано, что это число равно log_2(n!)+o(n). Тем самым улучшены ранее известные верхние оценки вида log_2(n!)+Theta(n). Новая оценка достигается при помощи предложенного метода групповых вставок.
