Efficient algorithm to produce the n-way intersection of sorted arrays in C

Question

I need to produce the intersection between some sorted arrays of integers in C. I know how to find the intersection between two sorted arrays, but I need to do this for more than two arrays, efficiently and without prior knowledge of the number of arrays. I can impose a sensible limit on the maximum number - let's say ten for now. These arrays could be anywhere from a few items to a couple of hundred thousand items long, and are by no means necessarily the same length.

Pseudo-code for producing the intersection of two sorted arrays:

while i < m and j < n do:
    if array1[i] < array2[j]:
        increment i
    else if array1[i] > array2[j]: 
        increment j
    else 
        add array1[i] to intersection(array1, array2)
        increment i
        increment j

I am working with C, and I am after a clear explanation rather than code.

Answer 1

You already have the logic for intersect on two arrays, so just call it multiple times.

Your intersect logic,

while i < m and j < n do:
if array1[i] < array1[j]:
    increment i
else if array1[i] > array2[j]: 
    increment j
else 
    add array1[i] to intersection(array1, array2)
    increment i
    increment j

Encapsulate the above code in an Intersect(int[] array1, int[] array2, int array1Length, int array2Length), that returns int[]. Call the method again on the result.

• Call1: int[] result = Intersect(array1, array2, array1Length, array2Length)
• Call2: result = Intersect(result, array3, resultArrayLength, array3Length)
• ...
• Call(n-1): result = Intersect(result, arrayn, resultArrayLength, arraynLength)

Possible optimizations:

• Continue with the calls only if the resultArrayLength > 0 (otherwise the interestion is a null set).
• In the intersect method compare the last element of array1 with the first element of array2, i.e.

EDITED if (array1[array1Length - 1] < array2[0]) return empty set (assuming that the arrays are sorted).