Для чётного количества чисел медианой считается полусумма двух средних чисел.
Данный алгоритм в лучшем случае находит медиану за 16 сравнений, а в худшем - за 18.
Вот его краткое описание:
Вначале разделим числа на две пятёрки и упорядочим каждую из них по возрастанию. Пусть ( к примеру ) третий элемент первой пятёрки меньше третьего элемента второй. Тогда мы можем отбросить два минимальных элемента первой четвёрки и два максимальных элемента второй четвёрки. Останутся две упорядоченные тройки. Сравниваем средние элементы этих троек и отбрасываем крайние числа аналогично тому, как это сделано в алгоритме для медианы шести чисел.
Если рассмотреть все 10! = 3628800 перестановок 10 чисел, то получим следующую статистику:

		16 -   16128
		17 -  451584
		18 - 3161088

В среднем получается 17.867 сравнений.

Алгоритм реализован в виде шаблона-функции:

template<class T> T _median10 ( const T * a )
{
    SemiRef<const T> a0(a[0]), a1(a[1]), a2(a[2]), a3(a[3]), a4(a[4]),
                     a5(a[5]), a6(a[6]), a7(a[7]), a8(a[8]), a9(a[9]);
// Упорядочивание первой пятёрки
    sort123 ( a0, a1, a2, a3, a4 );
// Упорядочивание второй пятёрки
    sort123 ( a5, a6, a7, a8, a9 );
// Отбрасывание крайних чисел и вычисление медианы
    if ( a2 < a7 )
    {
        if ( a3 < a6)
            return ( _max ( a3, a5 ) + _min ( a4, a6 ) ) / 2;
        else
            return ( _max ( a2, a6 ) + _min ( a3, a7 ) ) / 2;
    }
    else
    {
        if ( a1 < a8 )
            return ( _max ( a1, a7 ) + _min ( a2, a8 ) ) / 2;
        else
            return ( _max ( a0, a8 ) + _min ( a1, a9 ) ) / 2;
    }
}

Исходники находятся в файле median.h.