Finding the Median in Linear Time

Pick randomly a number a from A = {a₁, ..., a_n}.

Partition the n numbers into two sets:

• S - all the numbers smaller than a
• B - all the numbers bigger than a

If |S| = K-1 then a is the required K-median. Return a

If |S| < K-1 then the K-median lies somewhere in B. Call recursively to FindKMedian( B, K - |S| - 1 )

Else, call recursively to FindKMedian( S, K ).

Code from http://discuss.codechef.com/questions/1489/find-median-in-an-unsorted-array-without-sorting-it

int A[MAX],N;
int partitions(int low,int high)
{
    int p=low,r=high,x=A[r],i=p-1;
    for(int j=p;j<=r-1;j++)
    {
        if (A[j]<=x)
        {

            i=i+1;
            swap(A[i],A[j]);
        }
    }
    swap(A[i+1],A[r]);
    return i+1;
}
int selection_algorithm(int left,int right,int kth)
{
    for(;;)
    {
        int pivotIndex=partitions(left,right);          //Select the Pivot Between Left and Right
        int len=pivotIndex-left+1;

        if(kth==len)
            return A[pivotIndex];

        else if(kth<len)
            right=pivotIndex-1;

        else
        {
            kth=kth-len;
            left=pivotIndex+1;
        }
    }
}

Read full article from Finding the Median in Linear Time