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

		7 -  80 
		8 - 320
		9 - 320 

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

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

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

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