Пусть дано нечётное количество чисел. Обозначим его через n = 2k + 1. Будем считать, что все числа разные. Медианой считается то число из них, для которого есть k чисел меньше его и k чисел больше. Далее будут рассматриваться алгоритмы поиска медиан при небольших значений n.

Я уже знал об универсальном алгоритме, который находит медиану за линейное время, когда в 2004 году прочитал в 3-м томе "Искусства программирования" в разделе 5.3.3 о поиске медиан для конкретного небольшого количества чисел. Видимо я читал первое издание тома потому, что сейчас посмотрел второе - там этот раздел излагается немного по другому. Меня удивил тот факт, что для каждого количества чисел существует свой оптимальный алгоритм. Эта тема настолько захватила меня, что я стал писать свои алгоритмы для тех случаев, которых не было в книге.
Там были приведены примеры алгоритмов для поиска медиан с минимальным количеством сравнений для 5 чисел. Рассматривались два варианта: минимум для наихудшего случая и минимум в среднем. Средний случай определяется на основе всех перестановок n чисел. Всего их n!.

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

Второй алгоритм в наихудшем случае использует 7 сравнений, а в среднем - меньше 6.
Вначале берём три числа из пяти и упорядочиваем их по возрастанию. На это уйдёт 2 или 3 сравнения. Затем сравниваем оставшиеся два числа со средним из тройки. Если они оба больше, то медианой будет минимум из этих двух и максимума тройки. Если они оба меньше, то медианой будет максимум из этих двух и минимума тройки. Иначе медианой будет средний элемент тройки.
Если рассмотреть все 5! = 120 перестановок пяти чисел, то получим следующую статистику:
4 - 16
5 - 32
6 - 24
7 - 48
В среднем получается 5.867 сравнений.

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

В итоге у меня имеются алгоритмы поиска медиан от 3 до 13 чисел. Не все из них являются оптимальными. Какие именно сказать не могу, так как не знаю ответов.
Результаты сведены в таблицу:

Буквой a отмечены алгоритмы, которые ищут минимум в худшем случае, а буквой b - те, которые ищут минимум в среднем. Здесь использованы десятичные дроби с тремя знаками после точки и с округлением. На самом деле этих знаков больше.
Краткое описание этих алгоритмов находится здесь. Там же есть их реализация на С++.