возможно ли посчитать медиану не держа весь массив в памяти?

Только для сортированного массива 

Нет. Такие фокусы только с разными средними проходят. 

Да, но ведь существуют алгоритмы внешней сортировки, для которых не требуется загружать весь массив в оперативную память (а выгружая ненужные части массива во внешнюю память - например, на жесткий диск). Следовательно, можно надеяться на то, что существуют аналогичные алгоритмы внешнего нахождения медианы.

Если можно привлечь внешнюю сортировку - то собсно задача-то решена...

Это-то да, но тогда это стрельба из пушки по воробьям.

Существует множество алгоритмов поиска медианы. В том числе и без сортировки.

Эммм... почему, если не секрет? ведь по сравнению с реальной сортировкой алгоритм будет значительно упрощён - нам не требуется получить сортированный массив, требуется только найти средний элемент (или пару), следовательно, начальные и конечные элементы можно никуда не записывать, а только подсчитывать их количество.
Зримое улучшение можно искать, если  о массиве что-то заранее известно наверняка (например, что он ограничен сверху и снизу, что распределение элементов равномерное или нормальное и т.п.).

Добавлено через 4 минуты и 58 секунд
Pavia, но они многопроходны. И на больших массивах всё равно дают те же O(N*logN). Но обычно работают хуже при высокой неравномерности распределения значений по диапазону.

Akina, 
Есть алгоритмы за O(n), для любого массива.

Книга "Алгоритмы. Построение и анализ. Издание 2-е"

Вот хорошая статья на тему внешнего поиска медиан: "External Selection" (Jop F. Sibeyn): http://citeseerx.ist.psu.edu/viewdoc/downl...p1&type=pdf. Описаны рандомизированный и детерминированный алгоритмы, самый быстрый из которых - работает за N+o(N) операций чтения и o(N) операций записи.