Wie wäre es mit einer Kombination?
Erstmal die zwei kleinsten Dateien in den Speicher laden, und die Schnittmenge bilden. (Mit zwei Indizes, wie von generic erklärt)
Danach immer die nächste Datei in den Speicher laden und die bisherigen Einträge per binärer Suche in der Datei suchen.
Das laden der Datei könnte man noch in einen Thread auslagern. Ist aber fraglich ob sich das lohnt - die Datenmenge klingt nach einer Rechenzeit von 300ms. Die Synchronisation von Threads könnte das schon wieder verlangsamen.
Damit sollte die Schnittmenge schnell kleiner werden (damit die binäre Suche flott ist) aber am Anfang dürfte das Verfahren mit den zwei Indizes besser sein. Und solange es geht immer im
RAM arbeiten, und keine einzelnen Werte von der Platte lesen! Damit kann man jeden Algorithmus zum Schneckentempo zwingen. (ggf. ein Bandlaufwerk in Erwägung ziehen....)