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

Это сработает примерно со

Это сработает примерно со скоростью O(n), ибо без полного линейного просмотра a не обойдется. Параллельность я не рассмативаю, вы в этом последнем проходе сортировки с неизбежностью упретесь именно в bandwith памяти.

Т.е. выгодно становится если log(n)*m больше чем n (понятно что с изрядными коэффициентами, случайный доступ при бинарном поиске много дороже, чем последовательный доступ при слиянии).

Но мне кажется интересным такой вариант (при сравнительно небольших m): первые фазы бинарного поиска делаются делением на мультипроцессоры: допустим их 30, тогда каждый отвечает только за 1/30-ю входного массива А и за одну итерацию определяет с какими входными диапазонами работает данный конкретный мультипроцессор, после чего отвергает входное данное из b сразу (двумя сравнениями) не выполняя поиск.