Я думаю, что соответствующий алгоритм на псевдокоде можно изобразить как-то так:
Создадим массив из N элементов типа Node и проинициализируем его:
class Node {
int group;
int key;
int index;
}
Node[N] nodes;
for (int i = 0; i < N; i++) {
nodes[i].group = 0;
nodes[i].index = i;
}
Последовательность элементов с одинаковым значением поля group будем в дальнейшем называть группой. Таким образом, после инициализации мы имеем одну неотсортированную группу из N элементов.
Теперь будем сортировать этот массив в цикле по функциям, в каждой итерации мы будем ужесточать порядок в группах, которые содержат более одного элемента, т.е., еще не отсортированы:
for (int j = 0; j < M; j++) {
// для каждой группы, содержащей более одного элемента
// вычисляем значение ключа в каждом элементе этой группы
// сортируем на месте элементы этой группы по этому ключу
// разбиваем группу на подгруппы с одинаковым значением ключа, присваиваем подгруппам уникальные номера
// если все группы содержат ровно по одному элементу, то досрочный выход из цикла
}
Суть алгоритма в том, что после выполнения j-ой итерации массив nodes оказывается побит на группы, содержащие ровно по одному элементу, и группы, содержащие элементы, которые нельзя различить, используя только функции с номерами меньше j. При этом сами группы между собой упорядочены.
По-моему, очевидно, что лишних вызовов функций вычисления ключа в этом алгоритме нет.
После завершения цикла все элементы в массиве nodes отсортированы, для ссылки на элементы исходного массива используется значение поля index.
