Calculate median in c#

Looks like other answers are using sorting. That’s not optimal from performance point of view because it takes O(n logn) time. It is possible to calculate median in O(n) time instead. The generalized version of this problem is known as “n-order statistics” which means finding an element K in a set such that we have n elements smaller or equal to K and rest are larger or equal K. So 0th order statistic would be minimal element in the set (Note: Some literature use index from 1 to N instead of 0 to N-1). Median is simply (Count-1)/2-order statistic.

Below is the code adopted from Introduction to Algorithms by Cormen et al, 3rd Edition.

/// <summary>
/// Partitions the given list around a pivot element such that all elements on left of pivot are <= pivot
/// and the ones at thr right are > pivot. This method can be used for sorting, N-order statistics such as
/// as median finding algorithms.
/// Pivot is selected ranodmly if random number generator is supplied else its selected as last element in the list.
/// Reference: Introduction to Algorithms 3rd Edition, Corman et al, pp 171
/// </summary>
private static int Partition<T>(this IList<T> list, int start, int end, Random rnd = null) where T : IComparable<T>
{
    if (rnd != null)
        list.Swap(end, rnd.Next(start, end+1));

    var pivot = list[end];
    var lastLow = start - 1;
    for (var i = start; i < end; i++)
    {
        if (list[i].CompareTo(pivot) <= 0)
            list.Swap(i, ++lastLow);
    }
    list.Swap(end, ++lastLow);
    return lastLow;
}

/// <summary>
/// Returns Nth smallest element from the list. Here n starts from 0 so that n=0 returns minimum, n=1 returns 2nd smallest element etc.
/// Note: specified list would be mutated in the process.
/// Reference: Introduction to Algorithms 3rd Edition, Corman et al, pp 216
/// </summary>
public static T NthOrderStatistic<T>(this IList<T> list, int n, Random rnd = null) where T : IComparable<T>
{
    return NthOrderStatistic(list, n, 0, list.Count - 1, rnd);
}
private static T NthOrderStatistic<T>(this IList<T> list, int n, int start, int end, Random rnd) where T : IComparable<T>
{
    while (true)
    {
        var pivotIndex = list.Partition(start, end, rnd);
        if (pivotIndex == n)
            return list[pivotIndex];

        if (n < pivotIndex)
            end = pivotIndex - 1;
        else
            start = pivotIndex + 1;
    }
}

public static void Swap<T>(this IList<T> list, int i, int j)
{
    if (i==j)   //This check is not required but Partition function may make many calls so its for perf reason
        return;
    var temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}

/// <summary>
/// Note: specified list would be mutated in the process.
/// </summary>
public static T Median<T>(this IList<T> list) where T : IComparable<T>
{
    return list.NthOrderStatistic((list.Count - 1)/2);
}

public static double Median<T>(this IEnumerable<T> sequence, Func<T, double> getValue)
{
    var list = sequence.Select(getValue).ToList();
    var mid = (list.Count - 1) / 2;
    return list.NthOrderStatistic(mid);
}

Few notes:

1. This code replaces tail recursive code from the original version in book in to iterative loop.
2. It also eliminates unnecessary extra check from original version when start==end.
3. I’ve provided two version of Median, one that accepts IEnumerable and then creates a list. If you use the version that accepts IList then keep in mind it modifies the order in list.
4. Above methods calculates median or any i-order statistics in O(n) expected time. If you want O(n) worse case time then there is technique to use median-of-median. While this would improve worse case performance, it degrades average case because constant in O(n) is now larger. However if you would be calculating median mostly on very large data then its worth to look at.
5. The NthOrderStatistics method allows to pass random number generator which would be then used to choose random pivot during partition. This is generally not necessary unless you know your data has certain patterns so that last element won’t be random enough or if somehow your code is exposed outside for targeted exploitation.
6. Definition of median is clear if you have odd number of elements. It’s just the element with index (Count-1)/2 in sorted array. But when you even number of element (Count-1)/2 is not an integer anymore and you have two medians: Lower median Math.Floor((Count-1)/2) and Math.Ceiling((Count-1)/2). Some textbooks use lower median as “standard” while others propose to use average of two. This question becomes particularly critical for set of 2 elements. Above code returns lower median. If you wanted instead average of lower and upper then you need to call above code twice. In that case make sure to measure performance for your data to decide if you should use above code VS just straight sorting.
7. For .net 4.5+ you can add MethodImplOptions.AggressiveInlining attribute on Swap<T> method for slightly improved performance.