Algorithm to recursively compute median of the union of two arrays.

median.js

function median(A,B,x,y) {
	/*
	Function that takes sorted arrays A and B and their medians x and y
	and returns the median of A.concat(B).

	x is assumed to be the median of A and y is assumed to be the median
	of B.

	Arrays are assumed to be the same length. (Arrays of differing length
	may be handled with a different recursion case.)

	The median of an even number of elements is assumed here to
	be given by average of the middle two values.
	*/

	// establish our base cases:
	// 1. if we have two minimal-length arrays, just
	// combine them in constant time and compute the median.
	if ((A.length == 2) && (B.length == 2)) {
		var combined = A.concat(B).sort();
		return 0.5 * (combined[1] + combined[2]);
	}
	// 2. otherwise, if the medians are equal, then the median
	// of our combined array is equal to that number.
	if (x == y)
		return x; // equivalently, could also return y

	// if neither base case applies, perform the recursion,
	// depending on which of the two medians is bigger:
	if (x > y) {
		var A_reduced = A.filter(function (n) {
			return (n <= x);
		});

		var B_reduced = B.filter(function (n) {
			return (n >= y);
		});

		if (A_reduced.length % 2 == 0) {
			var A_mid = (A_reduced.length / 2);
			var A_redMed = 0.5 * (A_reduced[A_mid] + A_reduced[A_mid + 1]);
		} else {
			var A_redMed = A_reduced[Math.floor(A_reduced.length / 2)];
		}

		if (B_reduced.length % 2 == 0) {
			var B_mid = (B_reduced.length / 2);
			var B_redMed = 0.5 * (B_reduced[B_mid] + B_reduced[B_mid + 1]);
		} else {
			var B_redMed = B_reduced[Math.floor(B_reduced.length / 2)];
		}

		return median(A_reduced, B_reduced, A_redMed, B_redMed);
	} else {
		var A_reduced = A.filter(function (n) {
			return (n >= x);
		});

		var B_reduced = B.filter(function (n) {
			return (n <= y);
		});

		if (A_reduced.length % 2 == 0) {
			var A_mid = (A_reduced.length / 2);
			var A_redMed = 0.5 * (A_reduced[A_mid] + A_reduced[A_mid + 1]);
		} else {
			var A_redMed = A_reduced[Math.floor(A_reduced.length / 2)];
		}

		if (B_reduced.length % 2 == 0) {
			var B_mid = (B_reduced.length / 2);
			var B_redMed = 0.5 * (B_reduced[B_mid] + B_reduced[B_mid + 1]);
		} else {
			var B_redMed = B_reduced[Math.floor(B_reduced.length / 2)];
		}

		return median(A_reduced, B_reduced, A_redMed, B_redMed);
	}
}

(function () {
	// demonstration of the above median function
	var A = [1,3,6,2,4,6,6,7,2,2];
	var B = [1,3,5,8,3,1,4,2,5,7];
	var A_sorted = A.sort();
	var B_sorted = B.sort();
	var x = (A_sorted[4] + A_sorted[5]) / 2;
	var y = (B_sorted[4] + B_sorted[5]) / 2;

	console.log(median(A_sorted, B_sorted,x,y));
	var concated = A.concat(B).sort();
	console.log((concated[9] + concated[10]) / 2);
})();