Antonio Gulli's coding playground

Divide integers in c classes using their log c leftmost bits. Assume there exist (Ah << c) | Al +
(Bh << c ) | Bl = X. For each choice of Ah we
compute Bh and go through the sequence creating
one hash table H for elements with high bits = Ah
and one sequence Z for elements with high bits = Bh.
Next, iterate over Z and query H for (X-Z[i]).
Using 32 bits integers and c = 2, it takes 4 passes.
Using 64 bits it will be surely longer, but one
can make some statistics.

Is it what you intended?

Suppose that we can store M ints in memory.
Partition the large file into N/(2*M) files, each
one holding M/2 ints. Before writing these M/2 integers, perform a quicksort in memory and write in sorted order. Hence we have created N/(2*M) sorted runs.

Allocate two arrays A[M/2], B[M/2]

for (i = 0; i < N/(2*M); i++) {

Load ints of file i into array A

for (j = i + 1; j < N/(2*M); j++) {
Load ints of file j into array B

for (k = 0; k < M/2; k++) {
f = BinarySearch in array B for the number x-A[k]

if (f) {
printf("found");
break;
}
}
}
}