/// <summary>
/// Finds the median in an array
/// Uses an efficient sorting on a copy of the array
/// </summary>
/// <param name="array">The array</param>
/// <returns>The median of the array</returns>
public static int SortBasedMedian(int[] array)
{
    int[] copy = (int[])array.Clone();
    Array.Sort(copy);
    return copy[copy.Length / 2];
}

/// <summary>
/// Finds the median in an array
/// Uses a counting method
/// </summary>
/// <param name="array">The array</param>
/// <returns>The median of the array</returns>
public static int CountingBasedMedian(int[] array)
{
    for (int i = 0; i < array.Length; i++)
    {
        int lessThen = 0, greaterThen = 0;
        for (int j = 0; j < array.Length; j++)
        {
            if (array[j] < array[i])
                lessThen++;
            else if (array[j] > array[i])
                greaterThen++;
        }
        if (lessThen == greaterThen)
            return array[i];
    }
    throw new Exception("Impossible!");
}