This is a special case of a selection algorithm that can find the $k$th smallest element of an array with $k$ is the half of the size of the array. There is an implementation that is linear in the worst case.
Generic selection algorithm
First let's see an algorithm
find-kth that finds the $k$th smallest element of an array:
pivot = random element of A
(L, R) = split(A, pivot)
if k = |L|+1, return pivot
if k ≤ |L| , return find-kth(L, k)
if k > |L|+1, return find-kth(R, k-(|L|+1))
split(A, pivot) returns
L,R such that all elements in
R are greater than
L all the others (minus one occurrence of
pivot). Then all is done recursively.
This is $O(n)$ in average but $O(n^2)$ in the worst case.
A better pivot is the median of all the medians of sub arrays of
A of size 5, by using calling the procedure on the array of these medians.
B = [median(A, .., A), median(A, .., A), ..]
pivot = find-kth(B, |B|/2)
This guarantees $O(n)$ in all cases. It is not that obvious. These powerpoint slides are helpful both at explaining the algorithm and the complexity.
Note that most of the time using a random pivot is faster.