From SubfireWiki

From December 27, 2007

Had an algorithms question: find the median of two lists.

Came up with the right algorithm:

median(A, B, N):
  if A[N/2] < B[N/2]:
     return median(A+N/2, B, N/2)
  else if A[N/2] > B[N/2]:
     return median(A, B+N/2, N/2)
  else:
     (OK to ignore this case for now)

But screwed up the correctness proof (which was requested). Should have said:

Without loss of generality, assume A[N/2] < B[N/2]. If M is between A below A[N/2], then here are more than N/2 items in A and N/2 items in B greater than it, so it can't be the median of the merged list. Similarly for M in B+N/2, so M must be in A above (or at) the N/2 position or in B below the N/2 position.