Blum-Floyd-Pratt-Rivest-Tarjan algorithm

Algorithm to find kth largest element from an unsorted array in linear time.

Step 1:  If the number of elements in an array is large .Divide the array into arrays each with 5 elements. n/5 arrays.

Step2 : Compute Median of these 5 elements. 
This you can do by sorting each group. 
as there are 5 elements in Each group sorting takes 5log5. For n/5 groups in total time taken is , n/5*5log5 ~ o(n)

Step 3: Collect Median of all in array .

Step 4: Recursively compute median of this array.

Step5: Use this Median as Pivot in QuickSelect

Median > half of these n/5 group medians. So median > n/10 , also each median in respective group is greater then half element so in total median is greater then 
3n/10 element. So in total median is greater then 3n/10 and lesser then 3n/10 element 


So worst case of algorithm will obey T(n) O(n)+ T(n/5)+ T(7n/10).

Resulting in tn = O(n)


IF N IS LARGE ENOUGH DEVIDE THE LIST INTO N/5 LISTS OF 5 ELEMENTS 

public void floydAlgorithm(int []list_of_elements,int k){
//for n(array length) large enough in the range of 30 elements
m = n/5; //no of lists
int meA[] = new int[m];
for(int i=1 to m){
meA[i] = Median_of_5_Lists(5i-4...5i);
MOM = floydAlgorithm(meA,m/2);
r = Partition(list_of_elements,MOM);
if(k<r) return floydAlgorithm(A[1...r-1],k);
else if(k>r)return floydAlgorithm(A[r+1..n],k-r);
else return mom;
}

}