Комментировать

>Индексом-указателем может

>Индексом-указателем может быть номер в массиве a[], тогда это бесплатно.

К сожалению это не так просто. При сортировке нужно хранить старое значение этого индекса.

>3б) группировкой значений b (в смысле последовательности обработки) таким образом, чтобы лукапы в a[] были совсем локальными и случайные чтения заменялись бы линейными (подряд)

Это собственно я и предложил, когда писал о вспомогательных массивах, в которых хранятся каждое 32 (32^2, 32^3, 32^4) значение исходного отсортированного.