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

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

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

Но давайте на проблему с другой стороны посмотрим.
1) Данных много, полный индекс в быстрой памяти не построить. Что бы мы не делали, это будет вариация на тему бинарного поиска, log(n) лукапов на каждый входной элемент, чудес нет.
2) Каждый случайный доступ в a[] - долгий. Т.е. мы можем попрятать latency в то, что на SP будет много блоков, но больших чудес не будет, ограничивает в любом случае лукап в глобальной памяти.
3) Поэкономить эти лукапы можно двумя способами
3a) созданием части индекса в быстрой памяти каким-то образом
3б) группировкой значений b (в смысле последовательности обработки) таким образом, чтобы лукапы в a[] были совсем локальными и случайные чтения заменялись бы линейными (подряд)

3б имеет смысл при относительно больших m, когда полная сортировка слиянием еще невыгодна, но вероятность попасть в близкие куски a[] уже довольно большая (считая что позиционирование в 100 раз медленнее линейного чтения, m должна быть больше чем n/100)

Заметим, что задача очень похожа на типичный базоданновый поиск, только вместо диска у нас - медленная глобальная память (но суть та же - позиционирование медленное, чтение-запись быстрые), а вместо кэша в просто памяти - кэш в быстрой памяти (shared/регистры). Ничто не ново под луною.