Первый алгоритм median9a в лучшем случае находит медиану за 13 сравнений, а в худшем - за 14. Если рассмотреть все 9! = 362880 перестановок 9 чисел, то получим следующую статистику:

		13 - 104960
		14 - 257920

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

Второй алгоритм median9b в лучшем случае находит медиану за 10 сравнений, в худшем - за 16. Подробнее:

		10 -  2560
		11 - 20480
		12 - 63360
		13 - 97280
		14 - 87040
		15 - 61440
		16 - 30720

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

Вот его краткое описание. Вначале исходные 9 чисел разбиваются на 3 тройки и каждая тройка упорядочивается. Затем упорядочиваются средние элементы каждой тройки. После этого мы можем отбросить 4 числа ( два из них больше 6 чисел и два меньше 6 чисел ). Остаются 5 чисел: средняя тройка и ещё два числа. С ними мы поступаем, как в алгоритме median5b.

В моих тестах алгоритм median9b работал на несколько процентов быстрее, чем median9a.

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

template<class T> inline T _median9a ( const T * a ) ...
template<class T> inline T _median9b ( const T * a ) ...

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