Fun problem, conceptually easy but very prone to off-by-one errors. I think it's a bit easier to implement median using kth. Also it doesn't need recursion, one loop with fixed space usage is enough. Here's my JS code:<p><pre><code> function kth2(a,b,k) {
var ai=0,aj=a.length,bi=0,bj=b.length,d=1;
while (true) {
if (ai==aj) return b[bi+d*k];
if (bi==bj) return a[ai+d*k];
var m=d*(aj-ai),n=d*(bj-bi);
if (k<(m+n)/2) [ai,aj,bi,bj,d,k] = [aj-d,ai-d,bj-d,bi-d,-d,m+n-1-k];
var ak=Math.floor((m+1)/2),bk=Math.floor((n+1)/2);
if (d*a[ai+d*ak-d]<d*b[bi+d*bk-d]) [ai,k] = [ai+d*ak,k-ak];
else [bi,k] = [bi+d*bk,k-bk];
}
}
function median2(a,b) {
var n = a.length+b.length;
if (n%2 == 1) return kth2(a,b,(n-1)/2);
else return (kth2(a,b,n/2-1)+kth2(a,b,n/2))/2;
}</code></pre>