Здравствуйте.
Читаю статью с e-maxx. Вот кусок кода:
for (int i=0; i<n; ++i) {
pn[i] = p[i] - (1<<h);
if (pn[i] < 0) pn[i] += n;
}
memset (cnt, 0, classes * sizeof(int));
for (int i=0; i<n; ++i)
++cnt[c[pn[i]]];
for (int i=1; i<classes; ++i)
cnt[i] += cnt[i-1];
for (int i=n-1; i>=0; --i)
p[--cnt[c[pn[i]]]] = pn[i];
Почему в p[] будет содержаться перестановка для циклических сдвигов длины 2k после этой сортировки? Мы же просто отсортили вторые половинки..
Отсортировали не вторые, а первые половинки, и стабильной сортировкой, насколько я понимаю, а значит при равенстве первых половинок порядок остаётся прежним — отсортированным по вторым половинкам.