Можно попробовать вариант слияния (см. сортировку слиянием), когда вы храните по индексу от каждого массива и увеличиваете (на один) каждый раз тот, который указывает на минимальный элемент (если таких несколько, то увеличиваете все из них). Если было обновлено более одного индекса, то увеличиваете на единицу длины общих частей соответствующих пар массивов (нужна матрица длин пересечений). Плюс этого алгоритма — вы проходите по каждому массиву ровно один раз…
