I found the following online.
The required kth smallest element lies within A[1]...A[k] or B[1]...B[k]. Consider the following algorithm foo():
Input:
a sorted array A
an index I_A in A
a sorted array B
an index I_B in B
an integer k
Output: The kth smallest element in the union of A[I_A]...A[I_A + k - 1] and B[I_B]...B[I_B + k - 1].
Clearly the solution to our problem is foo(A, 1, B, 1, k).
The following is an implementation of foo():
Code:
int foo(int A[], int I_A, int B[], int I_B, int k)
{
if(k == 2) return the second smallest among A[I_A], A[I_A + 1], B[I_B] and B[I_B + 1];
int M_A = A[I_A + floor(k/2)];
int M_B = B[I_B + floor(k/2)];
if (M_A < M_B)
return foo(A, I_A + floor(k/2), B, I_B, ceil(k/2));
else
return foo(A, I_A, B, I_B + floor(k/2), ceil(k/2));
}