> Can anyone recommend a good algorithm for calculating medians. N may be quite
> large (> 1000).

Here are a two ways to compute medians and other order statistics on large
inputs without sorting the entire input:

1) Quicksort's partitioning method provides a good foundation for a recursive
method (this follows Sedgewick, Algorithms in C):

// return the k-th order statistic
select(int a[], int left, int right, int k)
{
  int i;
  if(right > left)
  {
    i = partition(left, right);
    if (i > left+k-1) select(a, left, i-1, k);
    if(i < left+k-1) select(a,i+1,right,k-i);
  }
}

where partition rearranges the array 'a' and returns i such that a[1]...a[i-1]
<= a[i] <= a[i+1]...a[N].  This method returns the k-th order statistic in
linear time, on average.


2) An alternative which averages about the same computation time but can use
much less memory is Rousseeuw's remedian: "Assume that n = b^k. ... The remedian
with base b proceeds by computing medians of groups of b observations (probably
with the above method), yielding b^{k-1} estimates on which the procedure is
iterated...until a single estimate remains."  Typically, we choose b odd so that
the median is simpler to compute (no averaging needed).  See: "The Remedian: A
Robust Averaging Method for Large Data Sets," Peter J. Rousseeuw, JASA, March
1990, Vol. 85, No. 409, Theory and Methods.  The method is shown to be a
consistent estimator of the population median that also maintains good breakdown
properties.