Быстрая сортировка Хоара

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

Сортировка будет работать и при использовании произвольного элемента - первого, последнего, среднего по индексу, или со случайным индексом.

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