To Find the median of an unsorted array

Question Detail: 

To fine the median of an unsorted array, we can make a min-heap in $O(n\log n)$ time for $n$ elements, and then we can extract one by one $n/2$ elements to get the median. But this approach would take $O(n \log n)$ time.

Can we do the same by some method in $O(n)$ time? If we can, then please tell.

Asked By : Luv

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1914

Answered By : jmad

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 element of an array:

find-kth(A, k)   pivot = random element of A   (L, R) = split(A, pivot)   if k = |L|+1, return A[k]   if k ≤ |L|  , find-kth(L, k)   if k > |L|+1, find-kth(R, k-(|L|+1)) 

The function split(A, pivot) returns L,R such that all elements in R are greater than pivot and 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.

Linear worst case: the median-of-medians algorithm

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.

find-kth(A, k)   B = [median(A[1], .., A[5]), median(A[6], .., A[10]), ..]   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.