Find the kth largest element of an array
Here is the median of medians algorithm which also takes \$O(n)\$ in the worst cases:


Divide the array into \$\frac{n}{5}\$ lists of 5 elements each.
Find the median in each sub array of 5 elements.
Recursively ﬁnd the median of all the medians, let's call it \$M\$.
Partition the array into two sub array 1st sub-array contains the elements larger than \$M\$. Let's say this sub-array is \$a1\$, while other sub-array contains the elements smaller than \$M\$. Let's call this sub-array \$a2\$.
If \$k \le |a1|\$, return selection(a1,k).
If \$k− 1 = |a1|\$, return \$M\$.
If \$k \gt |a1| + 1\$, return selection(a2,k −a1 − 1).


Let's see an interesting example of this where we have to find out the median of unsorted array in linear time. This may sounds NO at first look because median of array is middle element in sorted array if array is of odd length and middle of two middle elements if array is even length.

We can do it using quick/heap sort which takes \$O(nlogn)\$ time, but can we improve? Yes, have you heard about counting sort, which takes \$O(n)\$ time but extra \$O(Max−Min+1)\$ space, where Max and Min are the element of the array?

What if the array is ar[]={10000000,200000000}. Waste of space, right? But if you think about the median, which is nothing but the middle element of the array, where \$k = \frac{n}{2}\$ if array is odd length, can you see anything now? The median is nothing but \$\frac{n}{2}\$th smallest element in the array.

Great, so we got it. We can call median of medians algorithm up to \$k = \frac{n}{2}\$ and we can return ar[n/2] as the median.

Here's the pseudocode for the same:

//selects the median of medians in an array

static int selection(int a[], int s, int e, int k)

{

   // if the partition length is less than or equal to 5

   // we can sort and find the kth element of it

   // this way we can find the median of n/5 partitions

   if(e-s+1 &lt;= 5)

   {

       Arrays.sort(a,s, e);

       return s+k-1;

   }

   /* if array is bigger we partition the array in sub-arrays of size 5
   no. of partitions = n/5 = (e+1)/5 iterate through each partition and
   recursively 
   calculate the median of all of them and keep putting the medians in the 
   starting of the array 
   */

   for(int i=0; i&lt;(e+1)/5; i++)

   { 

      int left = 5*i;

      int right = left + 4;

      if(right &gt; e) right = e;

      //left+(right-left)/2 median will be 3rd element e.g.ar[2] in zero index based array

      int median = selection(a,left, right, 2); 

      swap(a[median], a[i]);

   }

  /*now we have array  a[0] = median of 1st 5 sized partition a[1] = median of 
  2nd 5 sized partition and so on till n/5 to find out the median of these n/5 
  medians we need to select the n/10th element of this set (i.e. middle of it)
 */

   return selection(a, 0, (e+1)/5, ((e+1)/10));

}


Call this function as:

selection(ar,0,ar.length-1,k) //k=n/2 which is median


Analysis of algorithm:

Dividing the array by 5 assures a worst-case split of 70-30 and at-least half of the medians are greater than the median-of-medians, hence at-least half of the \$\frac{n}{5}\$ blocks have at-least 3 elements and this gives a \$\frac{3n}{10}\$ split, which means the other partition is \$\frac{7n}{10}\$ in the worst case. That gives a time complexity of \$T(n) = T(\frac{n}{5}) + T(\frac{7n}{10}) + O(n)\$.

More reading:


Page on indstate.edu
The Median-of-Medians Algorithm | Hacker News